Implementing a Binary Heap in JavaScript

Introduction

A binary tree is a hierarchical structure where each node has at most two children, typically represented by a root, internal nodes, and leaf nodes. A binary heap is a special kind of complete binary tree that satisfies the heap property and is widely used for priority queues and sorting.

Relationship between Binary Tree and Binary Heap

Understanding binary heaps improves efficiency when working with array operations such as sorting. A binary heap can be viewed as a complete binary tree stored in an array, where parent and child indices follow simple arithmetic formulas.

Binary Tree Features

Root node: the topmost node of the tree.

Internal node: a node that has at least one child.

Leaf node: a node without any children.

Binary Tree Classification

Binary trees are classified into full binary trees and complete binary trees.

Full binary tree: a tree of depth k with exactly 2^k − 1 nodes.

Complete binary tree: all levels are fully filled except possibly the last, which is filled from left to right.

Binary Tree Indexing

When stored in an array, a node at index i has:

Left child at i * 2 + 1

Right child at i * 2 + 2

Leaf nodes when i >= Math.floor(N / 2) (where N is the array length).

Binary Heap Characteristics

A binary heap is a complete binary tree where each parent node is ordered with respect to its children (either all parents are greater than or equal to their children for a max‑heap, or less than or equal for a min‑heap).

Binary Heap Types

Max‑heap: the root holds the maximum key, and every parent is greater than its children.

Min‑heap: the root holds the minimum key, and every parent is smaller than its children.

How to Implement a Binary Heap

The following sections show a step‑by‑step JavaScript implementation of a max‑heap, including initialization, heapify, building the heap, sorting, insertion, and deletion.

Heap Initialization

class Heap {
  constructor(arr) {
    this.data = [...arr];
    this.size = this.data.length;
  }
}

Parent‑Child Swap (maxHeapify)

maxHeapify(i) {
  let max = i;
  if (i >= this.size) return;
  const l = left(i);
  const r = right(i);
  if (l < this.size && this.data[l] > this.data[max]) max = l;
  if (r < this.size && this.data[r] > this.data[max]) max = r;
  if (max === i) return;
  swap(this.data, i, max);
  return this.maxHeapify(max);
}

Building the Max‑Heap

rebuildHeap() {
  const L = Math.floor(this.size / 2);
  for (let i = L - 1; i >= 0; i--) {
    this.maxHeapify(i);
  }
}

Heap Sort (producing an ascending array)

sort() {
  for (let i = this.size - 1; i > 0; i--) {
    swap(this.data, 0, i);
    this.size--;
    this.maxHeapify(0);
  }
}

Insertion

insert(key) {
  this.data[this.size++] = key;
  if (this.isHeap()) return;
  this.rebuildHeap();
}

Deletion

delete(index) {
  if (index >= this.size) return;
  this.data.splice(index, 1);
  this.size--;
  if (this.isHeap()) return;
  this.rebuildHeap();
}

Utility Functions

function left(i) { return i * 2 + 1; }
function right(i) { return i * 2 + 2; }
function swap(A, i, j) { const t = A[i]; A[i] = A[j]; A[j] = t; }

Example Usage

const arr = [15,12,8,2,5,2,3,4,7];
const heap = new Heap(arr);
heap.rebuildHeap(); // build max‑heap
heap.sort(); // sort to ascending order
console.log(heap.data); // [2,2,3,4,5,7,8,12,15]

Conclusion

The article introduced binary trees and binary heaps, explained their properties, and provided a full JavaScript implementation that can be used for sorting, priority queues, and other algorithmic tasks.