Heap Data Structure min heap, max heap, Priority Queue

Array Representation

A binary heap is a complete binary tree stored compactly in an array. A min-heap keeps each parent no greater than its children; a max-heap reverses that rule. The root is the only globally ordered element.

For a zero-based array, parent(i) is floor((i - 1) / 2), left(i) is 2i + 1, and right(i) is 2i + 2. Completeness means every level is full except possibly the last, which fills left to right, so no child pointers are required.

Insert and Remove Root

Insertion appends at the next array position and sifts upward while the parent violates the heap property. Removing the root swaps in the final element, shortens the array, and sifts downward with the better-priority child. Both operations are O(log n); peek is O(1).

Build Heap and Heap Sort

Calling sift-down from the last internal node back to the root builds a heap in O(n), which is better than inserting n values independently. Heap sort repeatedly moves the root to the end and restores the heap; it is O(n log n), in-place, and normally unstable.

Priority Queue Boundaries

A heap is a common priority-queue implementation, but equal priorities need an explicit tie rule if stable order matters. Updating arbitrary priorities requires locating the item, often through an auxiliary index map. A heap does not support fast search for an arbitrary value.

Min-Heap Sift Down

function siftDown(heap, index) {
        while (true) {
          const left = 2 * index + 1;
          const right = left + 1;
          let smallest = index;
          if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
          if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
          if (smallest === index) return;
          [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
          index = smallest;
        }
      }

Schedule the Smallest Priority First

Insertion restores the min-heap invariant by moving the new item toward the root.

Schedule the Smallest Priority First

function push(heap, value) {
  heap.push(value);
  let i = heap.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (heap[parent] <= heap[i]) break;
    [heap[parent], heap[i]] = [heap[i], heap[parent]];
    i = parent;
  }
}
const heap = []; [8,3,5,1].forEach(v => push(heap,v));
console.log(heap[0]);

Output

Heap order guarantees the root, not a fully sorted array.

Before you move on