Heap / Priority Queue

A heap is a complete binary tree satisfying the heap property:

• Min-heap: Parent ≤ children (smallest at root)
• Max-heap: Parent ≥ children (largest at root)

Node Definition (Array-Based)

// No explicit node class needed - use array
// For node at index i:
//   Left child: 2*i + 1
//   Right child: 2*i + 2
//   Parent: (i-1) / 2

Visual Example (Min-Heap)

Array:  [1, 3, 5, 7, 9, 8, 6]

Tree:
          1
        /   \
       3     5
      / \\   / \
     7   9 8   6

Index:  0  1  2  3  4  5  6

Java PriorityQueue

// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Min-heap with custom comparator
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

// Operations
minHeap.offer(5);     // Insert - O(log n)
int min = minHeap.poll();  // Extract min - O(log n)
int peek = minHeap.peek(); // View min - O(1)
int size = minHeap.size(); // Size - O(1)

Manual Heap Implementation

class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        heap = new int[capacity];
    }

    public void insert(int val) {
        if (size == capacity) throw new RuntimeException("Heap full");
        heap[size] = val;
        size++;
        siftUp(size - 1);
    }

    public int extractMin() {
        if (size == 0) throw new RuntimeException("Heap empty");
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        siftDown(0);
        return min;
    }

    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[i] < heap[parent]) {
                swap(i, parent);
                i = parent;
            } else break;
        }
    }

    private void siftDown(int i) {
        while (true) {
            int smallest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < size && heap[left] < heap[smallest]) smallest = left;
            if (right < size && heap[right] < heap[smallest]) smallest = right;
            if (smallest != i) {
                swap(i, smallest);
                i = smallest;
            } else break;
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

Heapify (Build Heap from Array) - O(n)

public void heapify(int[] arr) {
    int n = arr.length;
    // Start from last non-leaf node
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
}

private void siftDown(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        swap(arr, i, largest);
        siftDown(arr, n, largest);
    }
}

Complexity

Space: O(n)

Top K Elements

Find K largest elements using min-heap of size K:

public int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();  // Remove smallest
        }
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

Kth Largest Element

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}

Median Finder (Two Heaps)

class MedianFinder {
    PriorityQueue<Integer> maxHeap;  // Lower half
    PriorityQueue<Integer> minHeap;  // Upper half

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());  // Balance
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

Merge K Sorted Lists

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode list : lists) {
        if (list != null) pq.offer(list);
    }
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (!pq.isEmpty()) {
        curr.next = pq.poll();
        curr = curr.next;
        if (curr.next != null) pq.offer(curr.next);
    }
    return dummy.next;
}

Task Scheduler

public int leastInterval(char[] tasks, int n) {
    int[] count = new int[26];
    for (char c : tasks) count[c - 'A']++;

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int c : count) {
        if (c > 0) maxHeap.offer(c);
    }

    int intervals = 0;
    while (!maxHeap.isEmpty()) {
        int cycle = 0;
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            if (!maxHeap.isEmpty()) {
                int val = maxHeap.poll() - 1;
                if (val > 0) temp.add(val);
                cycle++;
            }
        }
        for (int val : temp) maxHeap.offer(val);
        intervals += maxHeap.isEmpty() ? cycle : n + 1;
    }
    return intervals;
}

When to Use Heap

• Top K / Kth element: min-heap of size K
• Merge sorted: K-way merge with min-heap
• Median maintenance: two heaps (max + min)
• Scheduling/priorities: process by priority
• Sliding window max/min: heap with lazy deletion