Card 05/ 09
Binary Min-Heap in Python, Java and TypeScript
A heap with push, pop and heapify, then heapq and PriorityQueue.
A binary min-heap fits in a small class that wraps an array: push appends and sifts up, pop moves the last item to the root and sifts down, and the constructor builds a heap from any starting items. This card covers that class in Python, Java and TypeScript, and the priority queue each language already provides, so you can tell when to write a heap and when to use the library's.
A min-heap is a complete binary tree stored level by level in an array, in which every parent is no larger than its children; the parent of index i is at (i - 1) // 2 and its children at 2i + 1 and 2i + 2. Each listing builds a heap from 9 4 7 1 8 2 6 bottom-up, pushes 3, then pops every item, and the highlighted lines are the loop that builds the heap, the start of push and pop, the move of the last item to the root, and the step of each sift. The Python and Java listings then repeat the work with the library.
One binary min-heap's build, push and pop, in each language
import heapq
class MinHeap:
def __init__(self, values=()):
self.items = list(values)
for i in range(len(self.items) // 2 - 1, -1, -1):
self._sift_down(i)
def __len__(self):
return len(self.items)
def peek(self):
return self.items[0]
def push(self, value):
self.items.append(value)
self._sift_up(len(self.items) - 1)
def pop(self):
smallest = self.items[0]
last = self.items.pop()
if self.items:
self.items[0] = last
self._sift_down(0)
return smallest
def _sift_up(self, i):
while i > 0:
parent = (i - 1) // 2
if self.items[parent] <= self.items[i]:
return
self.items[parent], self.items[i] = self.items[i], self.items[parent]
i = parent
def _sift_down(self, i):
size = len(self.items)
while 2 * i + 1 < size:
child = 2 * i + 1
if child + 1 < size and self.items[child + 1] < self.items[child]:
child += 1
if self.items[i] <= self.items[child]:
return
self.items[i], self.items[child] = self.items[child], self.items[i]
i = child
heap = MinHeap([9, 4, 7, 1, 8, 2, 6])
print("heapified:", heap.items)
heap.push(3)
print("after push 3:", heap.items)
print("pops:", [heap.pop() for _ in range(len(heap))])
library = [9, 4, 7, 1, 8, 2, 6]
heapq.heapify(library)
print("heapq.heapify:", library)
heapq.heappush(library, 3)
print("heapq pops:", [heapq.heappop(library) for _ in range(len(library))])heapified: [1, 4, 2, 9, 8, 7, 6]
after push 3: [1, 3, 2, 4, 8, 7, 6, 9]
pops: [1, 2, 3, 4, 6, 7, 8, 9]
heapq.heapify: [1, 4, 2, 9, 8, 7, 6]
heapq pops: [1, 2, 3, 4, 6, 7, 8, 9]import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class BinaryHeapCode {
static final class MinHeap {
private final List<Integer> items;
MinHeap(List<Integer> values) {
items = new ArrayList<>(values);
for (int i = items.size() / 2 - 1; i >= 0; i--) {
siftDown(i);
}
}
int size() {
return items.size();
}
int peek() {
return items.get(0);
}
void push(int value) {
items.add(value);
siftUp(items.size() - 1);
}
int pop() {
int smallest = items.get(0);
int last = items.remove(items.size() - 1);
if (!items.isEmpty()) {
items.set(0, last);
siftDown(0);
}
return smallest;
}
private void siftUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (items.get(parent) <= items.get(i)) {
return;
}
swap(parent, i);
i = parent;
}
}
private void siftDown(int i) {
int size = items.size();
while (2 * i + 1 < size) {
int child = 2 * i + 1;
if (child + 1 < size && items.get(child + 1) < items.get(child)) {
child++;
}
if (items.get(i) <= items.get(child)) {
return;
}
swap(i, child);
i = child;
}
}
private void swap(int a, int b) {
int held = items.get(a);
items.set(a, items.get(b));
items.set(b, held);
}
List<Integer> items() {
return items;
}
}
public static void main(String[] args) {
MinHeap heap = new MinHeap(Arrays.asList(9, 4, 7, 1, 8, 2, 6));
System.out.println("heapified: " + heap.items());
heap.push(3);
System.out.println("after push 3: " + heap.items());
List<Integer> pops = new ArrayList<>();
while (heap.size() > 0) {
pops.add(heap.pop());
}
System.out.println("pops: " + pops);
PriorityQueue<Integer> library = new PriorityQueue<>(Arrays.asList(9, 4, 7, 1, 8, 2, 6));
library.add(3);
List<Integer> polled = new ArrayList<>();
while (!library.isEmpty()) {
polled.add(library.poll());
}
System.out.println("PriorityQueue polls: " + polled);
}
}heapified: [1, 4, 2, 9, 8, 7, 6]
after push 3: [1, 3, 2, 4, 8, 7, 6, 9]
pops: [1, 2, 3, 4, 6, 7, 8, 9]
PriorityQueue polls: [1, 2, 3, 4, 6, 7, 8, 9]class MinHeap {
private readonly items: number[];
constructor(values: number[] = []) {
this.items = [...values];
for (let i = Math.floor(this.items.length / 2) - 1; i >= 0; i--) {
this.siftDown(i);
}
}
get size(): number {
return this.items.length;
}
peek(): number | undefined {
return this.items[0];
}
push(value: number): void {
this.items.push(value);
this.siftUp(this.items.length - 1);
}
pop(): number | undefined {
if (this.items.length === 0) {
return undefined;
}
const smallest = this.items[0];
const last = this.items.pop() as number;
if (this.items.length > 0) {
this.items[0] = last;
this.siftDown(0);
}
return smallest;
}
snapshot(): number[] {
return [...this.items];
}
private siftUp(i: number): void {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.items[parent] <= this.items[i]) {
return;
}
this.swap(parent, i);
i = parent;
}
}
private siftDown(i: number): void {
const size = this.items.length;
while (2 * i + 1 < size) {
let child = 2 * i + 1;
if (child + 1 < size && this.items[child + 1] < this.items[child]) {
child++;
}
if (this.items[i] <= this.items[child]) {
return;
}
this.swap(i, child);
i = child;
}
}
private swap(a: number, b: number): void {
[this.items[a], this.items[b]] = [this.items[b], this.items[a]];
}
}
const heap = new MinHeap([9, 4, 7, 1, 8, 2, 6]);
console.log(`heapified: [${heap.snapshot().join(", ")}]`);
heap.push(3);
console.log(`after push 3: [${heap.snapshot().join(", ")}]`);
const pops: number[] = [];
while (heap.size > 0) {
pops.push(heap.pop() as number);
}
console.log(`pops: [${pops.join(", ")}]`);heapified: [1, 4, 2, 9, 8, 7, 6]
after push 3: [1, 3, 2, 4, 8, 7, 6, 9]
pops: [1, 2, 3, 4, 6, 7, 8, 9]All three hand-written heaps printed the same arrays: 1 4 2 9 8 7 6 after the build, 1 3 2 4 8 7 6 9 after pushing 3, and the items in ascending order from the pops. Popping every item from a heap in this way is heapsort, which costs O(n log n).
Python's heapq module is not a class but a set of functions that treat an ordinary list as a min-heap: heapify builds one in place in O(n), and heappush and heappop cost O(log n). The run's heapify left the same array as the class. Nothing stops other code from appending to the list directly and breaking heap order, so keep the list private to the code that uses it.
Java's PriorityQueue is a min-heap ordered by each item's natural order, the order its compareTo method defines, or by a Comparator passed to the constructor. Its add and poll cost O(log n), and peek costs O(1). Its constructor that takes a collection builds the heap bottom-up. Iterating over it does not visit items in priority order: a run that added 5, 1 and 3 printed 1, 5, 3 from a for-each loop, which is the order of the array inside it, and 1, 3, 5 from repeated calls to poll.
TypeScript and JavaScript have no built-in heap. Sorting an array after every insert works for a handful of items but costs O(n log n) per insert, so a class like the one here is the usual answer, either written or taken from a package.
← → move through sections and cards