Heaps & Priority Queues — Complete Interview Guide

# Python — min-heap by default
import heapq
h = []
heapq.heappush(h, val)
heapq.heappop(h)      # removes and returns smallest
h[0]                  # peek min (no removal)
heapq.heapify(lst)    # O(n) in-place
# Max-heap: negate values
heapq.heappush(h, -val)

// C++ — max-heap by default
#include <queue>
priority_queue<int> maxH;           // max-heap
priority_queue<int, vector<int>, greater<int>> minH; // min-heap
maxH.push(val);
maxH.top();   // peek
maxH.pop();

// Java — min-heap by default
PriorityQueue<Integer> minH = new PriorityQueue<>();
PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
minH.offer(val);
minH.peek();   // O(1)
minH.poll();   // O(log n)

// JavaScript — no built-in heap; implement or use array + sort
// Common pattern: use sorted array for small inputs
// Or implement MinHeap class
class MinHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._bubbleUp(); }
    pop() { const top=this.h[0]; const last=this.h.pop(); if(this.h.length){this.h[0]=last;this._sinkDown();} return top; }
    peek() { return this.h[0]; }
    size() { return this.h.length; }
    _bubbleUp() { let i=this.h.length-1; while(i>0){const p=(i-1)>>1;if(this.h[p]<=this.h[i])break;[this.h[p],this.h[i]]=[this.h[i],this.h[p]];i=p;} }
    _sinkDown() { let i=0,n=this.h.length; while(true){let min=i,l=2*i+1,r=2*i+2;if(l<n&&this.h[l]<this.h[min])min=l;if(r<n&&this.h[r]<this.h[min])min=r;if(min===i)break;[this.h[i],this.h[min]]=[this.h[min],this.h[i]];i=min;} }
}

import heapq
def top_k_largest(nums, k):
    return heapq.nlargest(k, nums)

# Manual K-size heap (O(n log k)):
def top_k_manual(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap  # k largest elements

def kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]
# Or: partial sort with min-heap of size k

from heapq import heappush, heappop
lo = []  # max-heap (negate)
hi = []  # min-heap

def add_num(num):
    heappush(lo, -num)
    heappush(hi, -heappop(lo))   # ensure max(lo) <= min(hi)
    if len(lo) < len(hi):
        heappush(lo, -heappop(hi))

def find_median():
    if len(lo) > len(hi):
        return -lo[0]
    return (-lo[0] + hi[0]) / 2

def merge_k_sorted(lists):
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    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

# Assign k workers to tasks; each takes 1 unit; worker available after finish
import heapq
def schedule(tasks, k):
    heap = list(range(k))  # availability times (all 0 initially)
    heapq.heapify(heap)
    for task in tasks:
        earliest = heapq.heappop(heap)
        heapq.heappush(heap, earliest + task)
    return max(heap)

import heapq
def dijkstra(graph, src):
    dist = {src: 0}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')): continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    count = Counter(nums)
    # Max-heap by frequency
    return heapq.nlargest(k, count.keys(), key=count.get)