Heap

Heap / Priority Queue

Always get the min (or max) in O(log n). Python's heapq is a min-heap. Negate values for max-heap.

Min-Heap Visualizer
Array repr: []
Push values to build the heap. Parent is always smaller than children.

Heap vs Sorted Array

OperationSorted ArrayHeap
Build from n elementsO(n log n)O(n)
Get minO(1)O(1)
Remove minO(n)O(log n)
InsertO(n)O(log n)

Min-Heap Property

The Invariant
For every node, its value is ≤ all its descendants. The root is always the minimum. Stored as an array where parent(i) = (i-1)//2, left(i) = 2i+1, right(i) = 2i+2.
When to use a heap
Keywords: "K largest", "K smallest", "median of stream", "top K frequent", "kth from stream". Any time you need repeated access to the min or max without re-sorting.

Max-Heap in Python — Negate!

Python only has min-heap
To simulate max-heap: negate values on push, negate again on pop. Push 5 as -5. Pop gets -max, negate to get max back.
import heapq
# Max-heap trick: negate values
max_heap = []
heapq.heappush(max_heap, -5)   # push 5
heapq.heappush(max_heap, -3)   # push 3
-heapq.heappop(max_heap)          # returns 5 (max)

# Heap of tuples: (priority, value)
heapq.heappush(h, (2, 'task'))   # sorted by first element

K Largest + K Most Frequent

import heapq
from collections import Counter

# K Largest Elements — min-heap of size k
def k_largest(nums, k):
    return heapq.nlargest(k, nums)  # O(n log k)
# Manual: maintain min-heap of size k
def k_largest_manual(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)              # O(k)
    for n in nums[k:]:
        if n > heap[0]:
            heapq.heapreplace(heap, n)  # O(log k)
    return heap

# Top K Frequent Elements
def top_k_frequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count, key=count.get)

# Kth Largest — use min-heap size k
def kth_largest(nums, k):
    heap = heapq.nsmallest(k, nums)  # heap[0] = kth largest
    return heap[0]

LeetCode Problems

  • EasyKth Largest Element in ArrayMin-heap of size k
  • MediumTop K Frequent ElementsCounter + nlargest
  • MediumK Closest Points to OriginMax-heap of size k on distance
  • MediumTask SchedulerMax-heap on frequency
  • HardFind Median from Data StreamTwo heaps (max + min)
  • HardMerge K Sorted ListsMin-heap of k pointers