Cribsheet for Heap data structure

Tags: java python algorithm heap

Written by: Tushar Sharma

A heap is a specialized tree-based data structure that satisfies the heap property: for every node \(i\) other than the root, \(A[\text{parent}(i)] \ge A[i]\) (Max-Heap) or \(A[\text{parent}(i)] \le A[i]\) (Min-Heap).

Core Properties

• Structure: A nearly complete binary tree.
• Height: A heap of \(n\) nodes has height \(h = \lfloor \log n \rfloor\).
  • Bounds: \(2^h \le n \le 2^{h+1} - 1\).
• Representation (Array): Usually implemented as a 1-indexed array.
  • Root: \(A[1]\)
  • Parent(i): \(\lfloor i/2 \rfloor\)
  • Left(i): \(2i\)
  • Right(i): \(2i + 1\)
  • Fact: The leaves are the nodes indexed by \(\lfloor n/2 \rfloor + 1, \dots, n\).

Key Algorithms

1. Max-Heapify (\(O(\log n)\))

Assumes the left and right subtrees of node \(i\) are already max-heaps, but \(A[i]\) might be smaller than its children. It "bubbles down" \(A[i]\) to its correct position.

2. Build-Max-Heap (\(O(n)\))

Converts an unordered array into a max-heap by calling Max-Heapify on all non-leaf nodes in bottom-up order (from \(n/2\) down to \(1\)).

• Why \(O(n)\)? While \(O(n \log n)\) is an upper bound, the tight bound is \(O(n)\) because most nodes are near the leaves and only travel a small distance. The sum of heights is a convergent series: \(\sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}} O(h) = O(n)\).

3. Heapsort (\(O(n \log n)\))

1. Build a max-heap from the array.
2. Swap the root (max element) with the last element of the heap.
3. Reduce heapsize and call Max-Heapify on the new root.
4. Repeat until the heap is empty.

Priority Queue API

A Max-Priority Queue maintains a set \(S\) and supports:

• Insert(S, x): Adds element \(x\) (\(O(\log n)\)).
• Maximum(S): Returns the max element (\(O(1)\)).
• Extract-Max(S): Removes and returns the max element (\(O(\log n)\)).
• Increase-Key(S, x, k): Increases \(x\)'s value to \(k\) (\(O(\log n)\)).

Using Standard Libraries

• Java
• Python

// Min Heap (Default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

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

// Operations
minHeap.offer(10);    // Insert - O(log n)
minHeap.peek();       // Maximum - O(1)
minHeap.poll();       // Extract-Min - O(log n)

import heapq

# Min Heap (Default)
min_heap = []
heapq.heapify(min_heap) # O(n)

# Operations
heapq.heappush(min_heap, 10)  # Insert - O(log n)
heapq.heappop(min_heap)       # Extract-Min - O(log n)
min_heap[0]                    # Minimum - O(1)

# Max Heap: Use negative values

Common Patterns

1. Top K Elements: Use a Min-Heap of size \(K\).
2. Median from Stream: Use a Max-Heap (lower half) and a Min-Heap (upper half).
3. Greedy with Cooldown: Use a Max-Heap for the next best item and a Queue for items in cooldown.

---

comments powered by Disqus