Implement a binary heap (min & max) with array + sift up/down

Medium

Problem

Implement a binary heap stored in an array (parent at (i−1)/2, children at 2i+1 and 2i+2) with insert, extractMin (or extractMax), peek and heapify, using sift-up and sift-down.

Example 1

Input:  insert 5, 3, 8, 1 → extractMin() → peek()
Output: 1, 3

Also asked as: Implement a Maxheap/MinHeap using arrays and recursion · Convert min heap to max heap

Test cases

Case 1

Input:    new Heap()
.push(5)
.push(3)
.push(8)
.push(1)
.pop()
.peek()
Expected: [null,null,null,null,1,3]

Case 2

Input:    new Heap()
.push(2)
.push(2)
.push(1)
.pop()
.pop()
.pop()
.pop()
Expected: [null,null,null,1,2,2,null]

Case 3

Input:    new Heap()
.peek()
.pop()
Expected: [null,null]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Array-backed heap

Time push/pop O(log n), build O(n)Space O(n)

Parent of i is (i−1)>>1; children are 2i+1, 2i+2. push sifts up, pop swaps root with last and sifts down. "Heapify" an arbitrary array by sifting down every non-leaf from the middle back to 0 — that is how you turn a min-heap array into a max-heap.

class Heap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; } // min-heap by default
get size() { return this.a.length; }
peek() { return this.a[0]; }
push(x) {
const a = this.a; a.push(x);
let i = a.length - 1;
while (i > 0) { const p = (i - 1) >> 1; if (this.cmp(a[p], a[i]) <= 0) break; [a[p], a[i]] = [a[i], a[p]]; i = p; }
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) { a[0] = last; this.#down(0); }
return top;
}
#down(i) {
const a = this.a;
for (;;) {
let s = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < a.length && this.cmp(a[l], a[s]) < 0) s = l;
if (r < a.length && this.cmp(a[r], a[s]) < 0) s = r;
if (s === i) break;
[a[s], a[i]] = [a[i], a[s]]; i = s;
}
}
static heapify(arr, cmp) { const h = new Heap(cmp); h.a = arr; for (let i = (arr.length >> 1) - 1; i >= 0; i--) h.#down(i); return h; }
}
// Max-heap: new Heap((a, b) => b - a).