Table of Contents

• What is a Heap?
• Properties of Heaps
• What is a Priority Queue?
• Some trivial Problems and their Solutions Using Heaps
• 1. Finding the K Smallest Elements
• 2. Running Median from a Stream
• 3. Merge K Sorted Lists Efficiently
• Using Python’s heapq Library
• Building Your Own Heap: A Min-Heap Implementation from Scratch

What is a Heap?

Imagine a special kind of binary tree where the parent node always dominates its children, depending on the heap type:

• Min-Heap: Every parent node is smaller than or equal to its children. The smallest element is always at the root.
• Max-Heap: Every parent node is greater than or equal to its children. The largest element lives at the root.

Heaps are complete binary trees, meaning they’re filled level by level, left to right, except possibly the last. Why does this matter? Because this property keeps operations efficient:

Properties of Heaps

What is a Priority Queue?

Think of a priority queue as a special kind of queue where items are served not in the order they arrive but based on their priority:

• Items with higher priority get served first.
• Can be implemented using heaps, because heaps efficiently track the highest or lowest priority.

Priority queues appear in many classic problems: finding shortest paths (Dijkstra’s algorithm), scheduling jobs, event simulation, and more.

Some trivial Problems and their Solutions Using Heaps

1. Finding the K Smallest Elements

Problem: Given an array, return the K smallest elements.
Approach: Use a max-heap that stores only K elements. The moment you find a smaller element, you eject the largest in the heap.

import heapq

def k_smallest(nums, k):
    max_heap = []
    for num in nums:
        heapq.heappush(max_heap, -num)  # Max-heap via negation
        if len(max_heap) > k:
            heapq.heappop(max_heap)
    return [-x for x in max_heap]

print(k_smallest([7, 10, 4, 3, 20, 15], 3))

2. Running Median from a Stream

Problem: Continuously receive numbers and output the median after each insertion.
Solution idea: Maintain two heaps:

• A max-heap for the smaller half of numbers.
• A min-heap for the larger half. Balance their sizes and compute median quickly.

3. Merge K Sorted Lists Efficiently

Problem: Merge multiple sorted lists into one sorted list.
Approach: Use a min-heap to keep track of the smallest elements from each list, popping and pushing as you move through them.

import heapq

def merge_k_sorted_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    result = []
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j+1], i, j+1))
    return result

print(merge_k_sorted_lists([[1,4,5],[1,3,4],[2,6]]))

Using Python’s heapq Library

Python’s heapq module implements a min-heap.

• Push an element: heapq.heappush(heap, val)
• Pop the smallest element: heapq.heappop(heap)
• heapq.heappushpop(heap, val) : Push and pop in one operation.
• heapq.heapreplace(heap, val) : Pop and push in one operation.
• heapq.nlargest(k, iterable, key=None) : Return the k largest elements from the iterable.
• heapq.nsmallest(k, iterable, key=None) : Return the k smallest elements from the iterable.
• Transform a list into a heap: heapq.heapify(list)

If you want a max-heap, just push negative values and remember to negate when popping.

Building Your Own Heap: A Min-Heap Implementation from Scratch

If you're still here, here’s a clean min-heap class that supports push and pop operations with proper heap property maintenance:

class MinHeap:
    def __init__(self):
        self.heap = []

    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 push(self, val):
        self.heap.append(val)
        self._heapify_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            return None
        root = self.heap[0]
        last_val = self.heap.pop()
        if self.heap:
            self.heap[0] = last_val
            self._heapify_down(0)
        return root

    def _heapify_up(self, i):
        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def _heapify_down(self, i):
        smallest = i
        left, right = self.left(i), self.right(i)
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self._heapify_down(smallest)

heap = MinHeap()
heap.push(10)
heap.push(4)
heap.push(15)
print(heap.pop())  # Outputs 4

To make a max-heap, simply reverse the comparison signs.