CoE KKU

มีหลายวิธีการที่จะสร้างโครงสร้าง priority queue เพื่อใช้งาน เราสามารถใช้โครงสร้างลิงค์ลิสต์ โดยให้การบรรจุเข้าที่ด้านหัว(front) ของลิสต์โดยมี running time เป็น $O(1)$ และต้องใช้การท่องไปในลิสต์เพื่อทำการลบค่าที่น้อยที่สุดด้วย running time $O(N)$

หรืออีกทางเลือกหนึ่งคือเพิ่มข้อกำหนดให้ค่าข้อมูลในลิสต์ต้องมีการจัดเรียงลำดับด้วย ซึ่งจะทำให้ running time ของบรรจุค่าเป็น $O(N)$ และ deleteMins เป็น $O(1)$

อีกทางเลือกของวิธีการที่จะสร้างโครงสร้าง priority queue เพื่อใช้งานคือการใช้ binary search tree ซึ่งการดำเนินการทั้ง 2 อย่างก็จะมี running time เฉลี่ยเป็น $O(log\ N)$ ถึงแม้ว่าการบรรจุค่าจะเป็นแบบสุ่มและการลบค่าจะไม่เป็นแบบสุ่มก็ตาม อย่าลืมว่าการลบค่าของเรานี้กระทำกับข้อมูลที่มีค่าที่น้อยที่สุด และการลบโนดในทรีย่อยซ้ายซ้ำ ๆ ก็จะทำให้ทรีเสียสภาพความสมดุลและทำให้ทรีย่อยขวามีน้ำหนักมากขึ้น แต่ก็เป็นการเพิ่ม expected depth ขึ้นด้วยค่าคงที่ที่ไม่มากเท่านั้นเอง

การใช้ search tree ดูจะเกินความจำเป็นไปทั้งนี้เนื่องจากมันสนับสนุนการทำงานอื่น ๆ ที่ไม่จำเป็น โครงสร้างพื้นฐานที่เราใช้นั้นไม่จำเป็นต้องใช้ตัวเชื่อม (linked structure) และการดำเนินงานทั้งสองที่กล่าวข้างบนเป็น $O(log\ n)$ ในกรณี worst-case และความจริงแล้วกรณีเฉลี่ยของการบรรจุก็ใช้เวลาเป็นค่าคงที่ (constant time) ในการ implement ของเราจะสามารถสร้าง heap ของหน่วยข้อมูล N ตัวได้ด้วย linear time ถ้าไม่มีการ delete แทรกแซง ในบทนี้ยังได้กล่าวถึงการ implement heaps ที่สนับสนุนการทำงานการควบรวม (merge) ที่มีประสิทธิภาพ