Skip to main content

Heap

Binary Heap​

  • used in HeapSort
  • it is a complete binary tree
  • used to implement Priority Queue
  • 2 types: Min heap; Max heap
    • Min Heap (highest priority item assigned lowest value)
    • Max Heap (highest priority item assigned highest value)

heapq​

import heapq
pq = [5, 20, 1, 30, 4]

heapq.heapify(pq)  # 1,4,5,30,20
heapq.heappush(pq, 3)  # 1,4,3,30,20,5
m = heapq.heappop(pq)  # 3,4,5,30,20 (removes min element)

heapq.nlargest(2, pq)  # [30,20]
heapq.nsmallest(2, pq)  # [1,4]

heapq.pushpop(pq, 2)
heapq.heapreplace(pq, -1)
note

Python implements heapq as min heap. To implement max heap multiply elements by -1 before storing


Min Heap​

  • complete binary tree
  • every node has value smaller than it's descendants
  • Array implementation:
    • parent = (i-1) // 2
    • left = 2i + 1
    • right = 2i + 2
class MinHeap:
    def __init__(self):
        self.mh = []

    def __init__(self, arr = []):
        self.mh = arr
        # bottom left internal node
        i = self.parent(len(arr) - 1)
        while i >= 0:
            self.minHeapify(i)
            i -= 1

    def parent(self, i):
        return (i - 1) // 2

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def insert(self, x):
        self.mh.append(x)
        i = len(self.mh) - 1
        while i > 0 and self.mh[self.parent(i)] > self.mh[i]:
            p = self.parent(i)
            self.mh[i], self.mh[p] = self.mh[p], self.mh[i]
            i = p

    def minHeapify(self, i):
        # fixes the heap whose root is violating the heap properties
        l = self.left(i)
        r = self.right(i)
        smallest = i
        n = len(self.mh)
        if l < n and self.mh[l] < self.mh[smallest]:
            smallest = l
        if r < n and self.mh[r] < self.mh[smallest]:
            smallest = r
        if smallest != i:
            self.mh[smallest], self.mh[i] = self.mh[i], self.mh[smallest]
            self.minHeapify(smallest)

    def extractMin(self):
        n = len(self.mh)
        if n == 0:
            return float("inf")
        res = self.mh[0]
        self.mh[0] = self.mh[n - 1]
        self.mh.pop()
        self.minHeapify(0)
        return res

    def decreaseKey(self, i, x):
        self.mh[i] = x
        while i != 0 and self.mh[self.parent(i)] > self.mh[i]:
            p = self.parent(i)
            self.mh[i], self.mh[p] = self.mh[p], self.mh[i]
            i = p

    def deleteKey(self, i):
        n = len(self.mh)
        if i >= n:
            return
        self.decreaseKey(i, float("-inf"))
        self.extractMin()