CoE KKU

มีการประยุกต์ใช้ priority queue ใน graph algorithms ได้อย่างมีประสิทธิภาพซึ่งจะได้กล่าวถึงในบทที่ 9 ในหัวข้อนี้จะแสดงตัวอย่างการใช้ priority queue ช่วยหาคำตอบของปัญหาการเลือก

ปัญหาแรกที่จะกล่าวถึงคือปัญหาการเลือกค่าที่ได้กล่าวมาแล้วในบทที่ 1 ตัวปัญหาคือ มีอินพุตเป็นรายการของค่าจำนวน N ค่า ซึ่งค่าทั้งหมดนี้สามารถนำมาจัดเรียงตามลำดับค่าได้ และมีค่า k เป็นเลขจำนวนเต็ม ปัญหาคือ ให้ทำการค้นหาตัวอินพุตที่มีค่ามากเป็นอันดับที่ k ในจำนวน N ค่านี้

ในบทที่ 1 ได้กล่าวถึงอัลกอริทึมในการแก้ปัญหานี้ไว้ 2 อัลกอริทึม แต่ทั้งสองอัลกอริทึมนั้นก็เป็นวิธีที่ไม่มีประสิทธิภาพที่ดี อัลกอริทึมแรกที่ได้กล่าวไปแล้วซึ่งเรียกว่า อัลกอริทึม 1A เริ่มด้วยการอ่านค่าสมาชิกทั้งหมดเข้ามาเก็บในอะเรย์แล้วทำการจัดเรียงตามลำดับค่า ก็จะได้ค่าสมาชิกที่ต้องการค้าหา ถ้าเราใช้การจัดเรียงลำดับค่าแบบ simple sorting algorithm ก็จะมี running time เป็น $O(N^2)$

อีกอัลกอริทึมหนึ่งซึ่งจะเรียกว่าอัลกอริทึม 1B เริ่มด้วยการอ่านค่าสมาชิกมาจำนวน k ตัวมาเก็บในอะเรย์แล้วจัดเรียงตามลำดับของค่า ก็จะได้ค่าที่น้อยที่สุดในอะเรย์นี้เป็นค่าที่อยู่ที่ตำแหน่ง k ของอะเรย์ จากนั้นให้อ่านค่าที่เหลือทีละตัว แล้วเทียบกับค่าที่อยู่ในตำแหน่ง k ของอะเรย์ ถ้าค่าที่อ่านเข้ามานั้นมีค่ามากกว่า ก็ให้ลบค่าที่ตำแหน่ง k นั้นออกไปและบรรจุค่าใหม่นั้นลงในตำแหน่งที่ถูกต้องตามลำดับของค่าลงในอะเรย์ซึ่งเวลานี้เหลือสมาชิกอยู่จำนวน k – 1 ตัว เมื่อจบการทำงาน สมาชิกที่อยู่ที่ตำแหน่ง k คือคำตอบ อัลกอริทึมนี้มี running time เป็น $O(N• k)$ ทั้งนี้เนื่องจาก ถ้าใช้ simple sorting algorithm กับสมาชิกในอะเรย์เริ่มต้นจำนวน k ตัว ก็จะมี running time เป็น $O(k^2)$ จำนวนสมาชิกที่เหลือที่จะต้องประมวลผลต่อ คือ N – k ตัว และถ้าแต่ละตัวที่อ่านเข้ามานี้ต้องทำการเลื่อนค่าข้อมูลในอะเรย์ (หรือกล่าวได้ว่าต้องทำการเปรียบเทียบค่าเป็นจำนวนครั้ง) k ตำแหน่งทุกตัวของการอ่านเข้ามา ก็หมายความว่าเราต้องใช้การเลื่อนตำแหน่งค่าข้อมูลทั้งสิ้นจำนวน $(N – k) • k$ ตำแหน่ง ดังนั้น running time ของอัลกอริทึมนี้จึงเท่ากับ $O(k^2) + O((N - k)k) = O(N• k)$ และถ้า $k = N/2$, อัลกอริทึมก็จะมี running time เป็น $O(N^2)$

อัลกอริทึม 6A

เพื่อให้ปัญหาง่ายขึ้น สมมุติให้เราต้องการหาค่าที่น้อยเป็นอันดับที่ k อัลกอริทึมที่ใช้ คือ อ่านค่าสมาชิกจำนวน N ตัวเข้าในอะเรย์ จากนั้นใช้อัลกอริทึม buildHeap กับอะเรย์นี้เพื่อสร้าง Min-Heap แล้วใช้ deleteMin เป็นจำนวน k ครั้ง และค่าหลังสุดที่ได้จากการทำ deleteMin คือ คำตอบที่ต้องการ และจะเห็นได้ว่าถ้าเราเปลี่ยน heap order เป็น Max-heap เราก็จะได้คำตอบของปัญหาการเลือกเดิมข้างบน worst-case timing ของอัลกอริทึมนี้ คือ ต้องใช้ $O(N)$ เพื่อสร้าง heap ถ้าเราใช้ buildHeap และต้องใช้ $O(log\ N)$ สำหรับการ deleteMin แต่ละครั้ง และเนื่องจากเราต้องใช้ deleteMin ทั้งสิ้นเป็นจำนวน k ครั้ง ดังนั้นจึงมี running time รวมของอัลกอริทึมคือ $O(N + k\ log\ N)$ ถ้าอันดับที่ต้องการ $k = O(N/log\ N)$ แล้ว running time ของการทำงานของอัลกอริทึมก็จะได้รับอิทธิพลจาก buildHeap เป็นหลัก และนั่นคือ $O(N)$ กล่าวสำหรับค่า k ที่มีขนาดใหญ่ ๆ แล้ว ก็จะมี running time เป็น $O(k\ log\ N)$ และถ้า $k = N/2$ จะได้ running time เป็น $\Theta(N\ log\ N)$

สังเกตเห็นได้ว่าถ้าเราใช้โปรแกรมนี้โดยมีค่า k = N และบันทึกค่าทุกค่าขณะที่มันถูกนำออกจาก heap เราก็จะได้ข้อมูลที่มีการจัดเรียง ด้วยเวลา $O(N\ log\ N)$ ในบทที่ 7 จะได้กล่าวถึงเรื่องนี้ในหัวข้อ heapsort

อัลกอริทึม 6B

กลับไปยังปัญหาเดิม คือ การหาค่าที่มากเป็นอันดับที่ k สำหรับอัลกอริทึมนี้เราจะใช้แนวคิดของอัลกอริทึม 1B กล่าวคือในเวลาใด ๆ เวลาหนึ่งเราจะคงสภาพ set S ที่ประกอบด้วยสมาชิกที่มีค่ามากที่สุด k ตัว หลังจากอ่านค่าสมาชิกจำนวน k ตัวแรกแล้ว เมื่อมีการอ่านสมาชิกตัวใหม่เข้ามาและเปรียบเทียบกับค่าสมาชิกที่เป็นค่ามากอันดับที่ k ซึ่งเราจะแทนด้วย $S_k$ เราจะเห็นได้ว่า $S_k$ ก็คือค่าที่น้อยที่สุดใน S ถ้าตัวที่อ่านเข้ามาใหม่นี้มีค่ามากกว่าก็ให้มันแทนที่ค่า $S_k$ ใน S นั่นคือ S จะมีค่าที่น้อยที่สุดตัวใหม่ซึ่งอาจจะเป็นค่าใหม่ที่ใส่เข้าไปหรือไม่ก็ได้ เมื่ออ่านค่าจนหมดแล้วจะพบว่าค่าที่น้อยที่สุดใน S คือคำตอบ

อัลกอริทึมนี้เหมือนกับอัลกอรอทึมที่กล่าวไปแล้วในบทที่ 1 เพียงแต่เราจะใช้ heap สำหรับการทำงาน S เราจะนำสมาชิกจำนวน k ตัวแรกบรรจุลงใน heap ด้วยเวลา $O(k)$ ด้วยการใช้ buildHeap เวลาที่ใช้ในการประมวลผลสมาชิกแต่ละตัวที่เหลือ คือ O(1) เพื่อตรวจค่าว่าจะบรรจุมันลงใน S หรือไม่ บวกกับเวลา $O(log\ k)$ เพื่อลบสมาชิก $S_k$ และบรรจุค่าใหม่ในกรณีที่ต้องบรรจุ ดังนั้น เวลาทั้งหมด คือ $O(k + (N – k )\ log\ k ) = O(N\ log\ k )$