MV's blog

Binary Heaps

Binary heap is a data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. A binary heap is defined as a binary tree with two additional constraints:

• Shape property: a binary heap is a complete binary tree; that is all levels of the tree except possibly the last one are fully filled, and if the last level of the tree is not complete, the nodes are filled from left to right
• Heap property: the key stored at each node is either greater than or equal to (>=) or less than or equal to (=<) the keys in the node's children, according to some total order.

Heaps where the parent key is greater than or equal to (>=) it's children are called max-heaps, those where it's less than or equal to (=<) are called min heaps.

The binary heap can be represented and constructed using arrays and simple arithmetics.

Operations

The binary heap supports inserting and deleting a min/max element from the heap.

Insertion

When inserting an element, we insert it at the end (k-th index) and try to "swim" it up the tree. We do that by comparing it with its parent which is located at index k / 2. If the element is greater than its parent (in a max heap) then we swap their places. We continue to do this until the parent is greater than the inserted element.

Deletion

When deleting an element, return the first element, and in its place in the heap put the last element. Tnen try to "sink" that element to its correct place by comparing it with its children at indexes 2 * k and (2 * k) + 1and swapping it with the greater child. Repeat until the element is greater than both its children.

Sample typescript implementation

/**
Implementable by comparable objects
*/
interface Comparable<T> {
  /**
   * Returns - 1 if this is greater than t,
   * 0 if equal,
   * 1 if this is less than this
   * @param  {T} t
   * @returns number
   */
  compareTo(t: T): number;
}

class MaxHeap<Item extends Comparable<Item>> {
  private items: Item[];
  private n: number;

  constructor() {
    this.n = 0;
  }

  public insert(item: Item): void {
    this.items[++this.n] = item;
    this.swim(this.n);
  }

  public deleteMax(): Item {
    const item = this.items[1];
    this.items[1] = this.items[this.n--];
    this.items[this.n + 1] = null;
    this.sink(1);

    return item;
  }

  /**
   * Try to swim the k-th element, i.e while it is smaller
   * than it's parent swap their places
   */
  private swim(k: number): void {
    while (
      k > 1 &&
      this.items[k].compareTo(this.items[k / 2]) === -1
    ) {
      const tmp = this.items[k];
      this.items[k] = this.items[k / 2];
      this.items[k / 2] = tmp;

      k = k / 2;
    }
  }

  /**
   * Try to sink the k-th element, i.e find the larger
   * of the two children * and if it's smaller than it,
   * swap their places, repeat until it is
   * larger than both children
   */
  private sink(k: number): void {
    while (2 * k <= this.n) {
      let j = 2 * k;

      if (
        j < this.n &&
        this.items[j].compareTo(this.items[j + 1]) === 1
      )
        j++;
      if (this.items[k].compareTo(this.items[j]) === -1) break;

      const tmp = this.items[k];
      this.items[k] = this.items[j];
      this.items[j] = tmp;

      k = j;
    }
  }
}