ดี-ฮีป

เป็นการคิดค้นโดย 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-oBest-caseWorst-caseหาตำแหน่งที่ต้องการ O(1) - -กรณีหาค่าที่มากที่สุด O(1) - -กรณีลบค่าที่มากที่สุด O(n)ไม่มีค่าใน heapมีค่าใน heapกรณีเพิ่มข้อมูล  O(n)ไม่มีค่าใน heap ก่อนหน้านี้มีค่าใน heapกรณีแสดงข้อมูล O(1) -  -
เนื่องจากหากรณีตำแหน่งที่ต้องการ, กรณีหาค่าที่มากที่สุด และกรณีแสดงข้อมูล ไม่มี best case และ worst case เนื่องจากเป็น O(1)

 อ้างอิง 
 https://people.ksp.sk/~kuko/gnarley-trees/?page_id=77 
 https://www.geeksforgeeks.org/k-ary-heap/

หมวดหมู่:ฮีป (โครงสร้างข้อมูล)