[heapq] Implementing Binary Heap in Python

1. What is Binary Heap?

A Binary Heap is a heap, a tree which obeys the property that the root of any tree is greater than or equals to all its children. The primary use of such a data structure is to implement a priority queue.

 

2. Implementing Binary Max Heap

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

 

3. Binary Min Heap with Library

• heapq.heapfy(x) : Convert list x into heap
• heapq.heappush(heap, item) : Push item to heap
• heapq.heappop(heap) : Pop the smalleset item from heap
• heapq.heappushpop(heap, item) : Push item to heap and pop the smallest item from heap

 

 

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