วิกิพีเดีย
ดี-ฮีป
เป็นการคิดค้นโดย Johnson (ปี 1975) D- Heap , D-ary Heap , m-ary Heap หรือ k-ary Heap คือ Heap ที่มี children node ไม่เกิน d node ซึ่งลำดับความสำคัญของแต่ละโหนดสูงกว่าลำดับความสำคัญของ children node
- ข้อดี -
- การใช้งานง่าย
- สำหรับขนาดเล็กd≥2เราจะได้โครงสร้างข้อมูลแคชที่มีประสิทธิภาพมากขึ้นและเป็นBinary Heap
- ขนาดใหญ่เป็นที่นิยมสำหรับโครงสร้างข้อมูล
code D-ary Heap
class D_aryHeap: def __init__(self, d): self.items = [] self.d = d def size(self): return len(self.items) def parent(self, i): return (i - 1)//self.d def child(self, index, position): return index*self.d + (position + 1) def get(self, i): return self.items[i] def get_max(self): if self.size() == 0: return None return self.items[0] def extract_max(self): if self.size() == 0: return None largest = self.get_max() self.items[0] = self.items[-1] del self.items[-1] self.max_heapify(0) return largest def max_heapify(self, i): largest = i for j in range(self.d): c = self.child(i, j) if (c < self.size() and self.get(c) > self.get(largest)): largest = c if (largest != i): self.swap(largest, i) self.max_heapify(largest) def swap(self, i, j): self.items[i], self.items[j] = self.items[j], self.items[i] def insert(self, key): index = self.size() self.items.append(key) while (index != 0): p = self.parent(index) if self.get(p) < self.get(index): self.swap(p, index) index = p return self.items def show(self): return self.items[:] testcase D-ary Heap
from daryheap2 import * # scenario1:เพิ่มค่า # Given:เพิ่มค่าเท่ากับ 2,7,10,1,5,6,8 # When:ทำการเพิ่มค่า # Then:ได้ผลลัพธ์คือ[[10, 8, 7, 1, 2, 5, 6] def test_case1(): d=3 dheap=D_aryHeap(d) dheap.insert(2) dheap.insert(7) dheap.insert(10) dheap.insert(1) dheap.insert(5) dheap.insert(6) dheap.insert(8) result=[10, 8, 7, 1, 2, 5, 6] assert dheap.show()==result # scenario2:ลบค่าที่มากที่สุด # Given:เพิ่มค่าเท่ากับ 2,6,11,8,13,16,4 # When:ลบค่าที่มากที่สุด # Then:ได้ผลลัพธ์คือ[13, 11, 6, 8, 2, 4] def test_case2(): d=3 dheap=D_aryHeap(d) dheap.insert(2) dheap.insert(6) dheap.insert(11) dheap.insert(8) dheap.insert(13) dheap.insert(16) dheap.insert(4) dheap.extract_max() result=[13, 11, 6, 8, 2, 4] assert dheap.show()==result # scenario3:หาค่าที่มากที่สุด # Given:เพิ่มค่าเท่ากับ 5,9,19,18,25,13,7 # When:หาค่าที่มากที่สุด # Then:ได้ผลลัพธ์คือ25 def test_case3(): d=3 dheap=D_aryHeap(d) dheap.insert(5) dheap.insert(9) dheap.insert(19) dheap.insert(18) dheap.insert(25) dheap.insert(13) dheap.insert(7) result=25 assert dheap.get_max()==result # scenario4:หาขนาด # Given:เพิ่มค่าเท่ากับ 6,9,5,11,31,2,23,1,4 # When:หาขนาด # Then:ได้ผลลัพธ์คือ9 def test_case4(): d=3 dheap=D_aryHeap(d) dheap.insert(6) dheap.insert(9) dheap.insert(5) dheap.insert(11) dheap.insert(31) dheap.insert(2) dheap.insert(23) dheap.insert(1) dheap.insert(4) result=9 assert dheap.size()==result # scenario5:หาค่าตำแหน่งที่กำหนด # Given:เพิ่มค่าเท่ากับ 7,14,19,22,1,5,3 หาตำแหน่งที่1 # When:หาค่าตำแหน่งที่กำหนด # Then:ได้ผลลัพธ์คือ7 def test_case5(): d = 3 dheap = D_aryHeap(d) dheap.insert(7) dheap.insert(14) dheap.insert(19) dheap.insert(22) dheap.insert(1) dheap.insert(5) dheap.insert(3) x=1 result=7 assert dheap.get(x)==result Big-o
| กรณี | Big-o | Best-case | Worst-case |
|---|---|---|---|
| หาตำแหน่งที่ต้องการ | O(1) | - | - |
| กรณีหาค่าที่มากที่สุด | O(1) | - | - |
| กรณีลบค่าที่มากที่สุด | O(n) | ไม่มีค่าในheap | มีค่าในheap |
| กรณีเพิ่มข้อมูล | O(n) | ไม่มีค่าในheapก่อนหน้านี้ | มีค่าในheap |
| กรณีแสดงข้อมูล | O(1) | - | - |
เนื่องจากหากรณีตำแหน่งที่ต้องการ ,กรณีหาค่าที่มากที่สุด ,กรณีแสดงข้อมูลไม่มีbest case และworst case เนื่องจากเป็นO(1)