Heap
What is a Heap?
A heap is a complete binary tree stored as an array that satisfies the heap property:
- Max-Heap — every parent is ≥ its children. Root = maximum element.
- Min-Heap — every parent is ≤ its children. Root = minimum element.
For a node at index i (0-indexed): left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
| Operation | Time | Description |
|---|---|---|
| peek (get min/max) | O(1) | Root is always min or max |
| insert | O(log n) | Add at end, bubble up |
| extract min/max | O(log n) | Remove root, sink down |
| build heap | O(n) | Heapify from bottom up |
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Min-Heap implementation
class MinHeap {
vector<int> heap;
void bubbleUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (heap[parent] <= heap[i]) break;
swap(heap[parent], heap[i]);
i = parent;
}
}
void sinkDown(int i) {
int n = heap.size();
while (true) {
int min = i, l = 2*i+1, r = 2*i+2;
if (l < n && heap[l] < heap[min]) min = l;
if (r < n && heap[r] < heap[min]) min = r;
if (min == i) break;
swap(heap[min], heap[i]);
i = min;
}
}
public:
void push(int val) { heap.push_back(val); bubbleUp(heap.size()-1); }
int pop() {
int top = heap[0];
heap[0] = heap.back(); heap.pop_back();
if (!heap.empty()) sinkDown(0);
return top;
}
int peek() { return heap[0]; }
bool empty() { return heap.empty(); }
};
int main() {
// Using STL priority_queue
priority_queue<int, vector<int>, greater<int>> minPQ;
for (int x : {5, 3, 8, 1, 9, 2}) minPQ.push(x);
cout << "Min: " << minPQ.top() << endl; // 1
while (!minPQ.empty()) { cout << minPQ.top() << " "; minPQ.pop(); }
cout << endl; // 1 2 3 5 8 9
// Custom MinHeap
MinHeap mh;
for (int x : {5, 3, 8, 1, 9, 2}) mh.push(x);
cout << "Custom min: " << mh.peek() << endl; // 1
cout << "Pop: " << mh.pop() << endl; // 1
// K largest elements using min-heap of size k
vector<int> nums = {3,1,4,1,5,9,2,6,5,3};
int k = 3;
priority_queue<int, vector<int>, greater<int>> kHeap;
for (int x : nums) {
kHeap.push(x);
if ((int)kHeap.size() > k) kHeap.pop();
}
cout << k << " largest: ";
while (!kHeap.empty()) { cout << kHeap.top() << " "; kHeap.pop(); }
cout << endl; // 5 6 9
return 0;
}import java.util.*;
public class HeapDemo {
public static void main(String[] args) {
// Min-heap (default in Java)
PriorityQueue<Integer> minPQ = new PriorityQueue<>();
for (int x : new int[]{5,3,8,1,9,2}) minPQ.offer(x);
System.out.println("Min: " + minPQ.peek()); // 1
while (!minPQ.isEmpty()) System.out.print(minPQ.poll() + " ");
System.out.println(); // 1 2 3 5 8 9
// Max-heap
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
for (int x : new int[]{5,3,8,1,9,2}) maxPQ.offer(x);
System.out.println("Max: " + maxPQ.peek()); // 9
// K largest elements
int[] nums = {3,1,4,1,5,9,2,6,5,3};
int k = 3;
PriorityQueue<Integer> kHeap = new PriorityQueue<>();
for (int x : nums) {
kHeap.offer(x);
if (kHeap.size() > k) kHeap.poll();
}
System.out.println("K largest: " + kHeap); // [5, 6, 9]
// Heap sort
int[] arr = {5,3,8,1,9,2};
PriorityQueue<Integer> sortHeap = new PriorityQueue<>();
for (int x : arr) sortHeap.offer(x);
System.out.print("Sorted: ");
while (!sortHeap.isEmpty()) System.out.print(sortHeap.poll() + " ");
System.out.println(); // 1 2 3 5 8 9
}
}import heapq
# Min-heap (Python's heapq is always min-heap)
nums = [5, 3, 8, 1, 9, 2]
heap = nums[:]
heapq.heapify(heap) # build heap in O(n)
print("Min:", heap[0]) # 1
# Push and pop
heapq.heappush(heap, 0)
print("After push 0:", heap[0]) # 0
print("Pop:", heapq.heappop(heap)) # 0
# Sort using heap
sorted_nums = []
while heap:
sorted_nums.append(heapq.heappop(heap))
print("Sorted:", sorted_nums) # [1, 2, 3, 5, 8, 9]
# Max-heap (negate values)
max_heap = [-x for x in [5, 3, 8, 1, 9, 2]]
heapq.heapify(max_heap)
print("Max:", -max_heap[0]) # 9
# K largest elements — O(n log k)
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
k = 3
print("K largest:", heapq.nlargest(k, nums)) # [9, 6, 5]
print("K smallest:", heapq.nsmallest(k, nums)) # [1, 1, 2]
# Manual k-largest with min-heap of size k
def k_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return sorted(heap, reverse=True)
print("K largest manual:", k_largest(nums, 3)) # [9, 6, 5]// Min-Heap implementation
class MinHeap {
constructor() { this.heap = []; }
push(val) {
this.heap.push(val);
this._bubbleUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this._sinkDown(0);
return min;
}
peek() { return this.heap[0]; }
size() { return this.heap.length; }
_bubbleUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.heap[parent] <= this.heap[i]) break;
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
}
}
_sinkDown(i) {
const n = this.heap.length;
while (true) {
let min = i, l = 2*i+1, r = 2*i+2;
if (l < n && this.heap[l] < this.heap[min]) min = l;
if (r < n && this.heap[r] < this.heap[min]) min = r;
if (min === i) break;
[this.heap[min], this.heap[i]] = [this.heap[i], this.heap[min]];
i = min;
}
}
}
const heap = new MinHeap();
[5, 3, 8, 1, 9, 2].forEach(x => heap.push(x));
console.log("Min:", heap.peek()); // 1
const sorted = [];
while (heap.size()) sorted.push(heap.pop());
console.log("Sorted:", sorted); // [1, 2, 3, 5, 8, 9]
// K largest elements
function kLargest(nums, k) {
const minHeap = new MinHeap();
for (const x of nums) {
minHeap.push(x);
if (minHeap.size() > k) minHeap.pop();
}
const result = [];
while (minHeap.size()) result.push(minHeap.pop());
return result.reverse();
}
console.log("K largest:", kLargest([3,1,4,1,5,9,2,6,5,3], 3)); // [9,6,5]