DSA: Heaps

Fundamentals of Heaps

Common Implementations Using Two Heaps

- Inserting Nums into Heaps

- Rebalancing Heaps

- Getting the Median of Two Heaps

Practice Problems

Learning Resources

---

Fundamentals of Heaps

A priority queue or heap is a data structure that consists of a collection of items and supports the following operations:

• insert: insert an item with a key

• delete_min/delete_max: remove the item with the smallest/largest key and returning it

There are two kinds of heaps - Min Heap and Max Heap. A Min Heap is a tree that has two properties:

1. almost complete, i.e. every level is filled except possibly the last(deepest) level. The filled items in the last level are left-justified.

2. for any node, its key (priority) is greater than its parent's key (Min Heap).

A Max Heap has the same property as #1 and opposite property as #2, i.e. for any node, its key is less than its parent's key.

Note: Before you can use heap functions you need to import:

Import heapq from * 
# or 
import heapq

heapq — Heap queue algorithm — Python 3.11.0 documentation

---

Common Implementations Using Two Heaps

Inserting number into minHeap or maxHeap

import heapq from *

  maxHeap = [] # contain the first half of the list
  minHeap = [] # contain the second half of the list

  #If there is nothing in the maxHeap or num is less than the number in   
  #the maxHeap, push num into maxHeap, else push into minHeap
  if not maxHeap or num <= -maxHeap[0]:
    heappush(maxHeap, -num)
  else:
    heappush(minHeap, num)

Rebalancing Heaps

def rebalance_heaps(self):
# either both the heaps will have equal number of elements or max-heap     will have one more element than the min-heap
  if len(self.maxHeap) > len(self.minHeap) + 1:
    heappush(self.minHeap, -heappop(self.maxHeap))
  elif len(self.maxHeap) < len(self.minHeap):
    heappush(self.maxHeap, -heappop(self.minHeap))
          

Getting the Median of Two Heaps

if len(maxHeap) == len(minHeap):
  return (-maxHeap[0] + minHeap[0]) / 2
else:
  return -maxHeap[0]

---

Practice Problems

Merge K Lists

 def merge_k_lists(lists):
  res = []
  heap = []

  for list in lists:
    heappush(heap, (list[0], list, 0))
  
  while heap:
    value, list, idx = heappop(heap)
    result.append(value)
    idx += 1
    if idx < len(list):
      heappush(heap, list[idx], list, idx)
  
  return res