Implement a binary heap (min & max) with array + sift up/down
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]
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).