Heap

In this chapter you will learn the basics of Heap data structure and how to apply it in a different problems.

A heap is a specialized tree-based data structure that satisfies the heap property. The heap property is defined as follows:

• In a max heap, for any given node i, the value of i is greater than or equal to the values of its children.
• In a min heap, for any given node i, the value of i is less than or equal to the values of its children.

Heaps are commonly used to implement priority queues, which are used in algorithms like Dijkstra's shortest path algorithm and the heap sort algorithm.

Problem

Given an array of integers, write a function to implement a heap data structure.

Example of usage:

let heap = new Heap();

heap.insert(3);
heap.insert(2);
heap.insert(1);
heap.insert(7);

console.log(heap.peek()); // 1

console.log(heap.extract()); // 1

console.log(heap.peek()); // 2

Solution

class Heap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  peek() {
    return this.heap[0];
  }

  extract() {
    const min = this.heap[0];
    const last = this.heap.pop();

    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown();
    }

    return min;
  }

  bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      let element = this.heap[index];
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.heap[parentIndex];

      if (parent <= element) break;

      this.heap[index] = parent;
      this.heap[parentIndex] = element;
      index = parentIndex;
    }
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild < element) {
          swap = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (swap === null && rightChild < element) ||
          (swap !== null && rightChild < leftChild)
        ) {
          swap = rightChildIndex;
        }
      }

      if (swap === null) break;

      this.heap[index] = this.heap[swap];
      this.heap[swap] = element;
      index = swap;
    }
  }
}

Complexity Analysis

• The time complexity of the insert and extract operations is O(log n) where n is the number of elements in the heap.
• The space complexity is O(n) since we are using an array to store the elements of the heap.

Practice

• Implement a priority queue using a heap.
• Implement a heap sort algorithm.
• Merge K sorted arrays using a heap.
• Find the kth largest element in an array using a heap.
• Find the kth smallest element in an array using a heap.
• Implement a heap using an array.