CoE KKU

d-heap มีลักษณะเดียวกับ binary heap ยกเว้นโนดใน d-heap มีโนดลูกได้มากที่สุดจำนวน d โนด (นั่นคือ binary heap ก็คือ 2-heap นั่นเอง)

รูปที่ 6.19 แสดงรูป 3-heap จะเห็นได้ว่า d-heap มีระดับความลึกที่น้อยกว่า binary heap มาก ดังนั้นจึงมี running time ที่ดีกว่า กล่าวคือมี running time ในการ inserts เป็น $O(log_d\ N)$ ซึ่งดีกว่ามาก อย่างไรก็ตามถ้า d มีขนาดใหญ่มาก การทำงาน deleteMin ก็เสียค่าใช้จ่ายมากกว่า เนื่องจากถึงแม้ว่ามีความลึกน้อยกว่า เราก็ต้องค้นหาค่าที่น้อยที่สุดของโนดลูก d โนด ซึ่งต้องใช้การเทียบค่าเป็นจำนวน d – 1 ครั้ง ทำให้ต้องใช้เวลาการทำงานเป็น $O(d\ log_dN)$ ถ้า d เป็นค่าคงที่ค่าหนึ่ง running times ก็จะเป็น $O(log\ N)$ ถึงแม้ว่าจะยังสามารถใช้อะเรย์สำหรับ d-heap ได้ แต่การคำนวณที่ต้องใช้การคูณและหารเพื่อหาตำแหน่งของโนดลูกและโนดแม่นั้นจะเป็นการใช้ค่า d (ยกเว้นว่าค่า d จะเท่ากับค่าของ 2 ยกกำลัง) ซึ่งจะทำให้ running time มีค่าสูงขึ้นเนื่องจากเราไม่สามารถใช้ bit shift สำหรับการหารได้เช่นเดียวกับที่มันเป็น binary heap การใช้ d-heap ยังเป็นทางเลือกที่น่าสนใจของการใช้ priority queue ในกรณีที่จำนวนข้อมูลมีมากจนไม่สามารถบรรจุลงในหน่วยความจำหลักได้ทั้งหมดในคราวเดียวเช่นเดียวกับสถานการณ์ที่เราใช้ B-tree

จุดด้อยที่เห็นได้ชัดของการใช้ heap คือนอกจากไม่สนับสนุนการทำงานการค้นหาได้ดีแล้ว การดำเนินการควบรวม heap เข้าด้วยกันก็เป็นเรื่องที่ยากมาก มีทางเลือกไม่มากในการใช้โครงสร้างสำหรับ heap ที่จะมี running time ในการควบรวม (merge) เป็น $O(log\ N)$ หัวข้อถัดไปจะกล่าวถึงโครงสร้างข้อมูล 3 แบบที่สนับสนุนการควบรวมที่มีประสิทธิภาพ