[DS] Heap

1. What is Heap?

A binary heap is a heap, a tree which obeys the property that the root of any tree is greater than or eqaul to all its children. The primary use of usch a data structure is to implement a priorty queue.

 

• heap[k] <= heap[2 * k + 1]
• heap[k] <= heap[2 * k + 2]

 

2. Implementation of Binary Heap

class MaxHeap: 
    def __init__(self): 
        self.head = [] 
       
    def _heapify(self, n, i): 
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if l < n and self.head[i] < self.head[left] : 
            largest = left 
        if r < n and self.head[largest] < self.head[right] : 
            largest = right 
            
        if largest != i : 
            self.head[i], self.head[largest] = self.head[largest], self.head[i] 
            self._heapify(n, largest)
            
    def insert(self, new): 
        size = len(self.head) 
        if size == 0 : 
            self.append(new) 
        else : 
            self.append(new)
            for i in range((size//2) - 1, -1, -1) : 
                self._heapify(size, i) 
                
    def delete(self, num) : 
        size = len(self.head)
        i = 0 
        for i in range(0, size) : 
            if num == self.head[i] : 
                break 
        
        self.head[i], self.head[size - 1] = self.head[size - 1], self.head[i]
        self.head.remove(num) 
        
        for i in range((size//2) -1, -1) : 
            self._heapify(len(self.head), i)

 

3. Library of Binary Heap (Min - Heap)

• heaoq.heappush(heap, item) : push item to heap
• heapq.heappop(heap) : pop the smallest item from heap
• heapq.heappushpop(heap, item) : push item to heap and pop the smallest item from heap
• heapq.heapify(x) : Convert list x into heap

https://docs.python.org/ko/3/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.10.6 문서