What is a Heap Tree

A heap is a special type of tree-based data structure that satisfies the heap property: the value of each node is always greater than or equal to the value of its parent, with the exception of the root node, which has no parent. There are two types of heaps: min heaps and max heaps. In a min heap, the value of each node is always greater than or equal to the value of its parent, while in a max heap, the value of each node is always less than or equal to the value of its parent.

Heaps are typically implemented using an array, where the parent and child nodes of each node are found using the following formulas:

• The index of the left child of a node at index i is 2 * i + 1
• The index of the right child of a node at index i is 2 * i + 2
• The index of the parent of a node at index i is (i - 1) / 2

For example, consider the following min heap:

This heap can be represented as a Max Heap array as follows: [20,12,18,8,11,7,5] This heap can be represented as a Min Heap array as follows: [5,11,7,20,18,12,8]

To insert a new element into a heap, we first add it to the end of the array and then percolate it up the heap until it is in the correct position. To do this, we compare the value of the new element with the value of its parent and swap them if necessary. This process is repeated until the heap property is satisfied.

To remove the minimum (or maximum) element from a min (or max) heap, we remove the root node and replace it with the last element in the array. We then percolate this element down the heap until it is in the correct position. To do this, we compare the value of the element with the values of its children and swap it with the smaller (or larger) child if necessary. This process is repeated until the heap property is satisfied.

Heaps are commonly used for implementing priority queues, where the priority of each element is represented by its value in the heap. They are also used in algorithms for sorting and searching data, such as heap sort and Dijkstra’s algorithm.

Overall, heaps are a useful data structure for efficiently storing and manipulating data in a tree-like structure, and they have many practical applications in computer science.

Here is an example implementation of a min heap class in JavaScript:

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

  getParentIndex(index) {
    return Math.floor((index - 1) / 2)
  }

  getLeftChildIndex(index) {
    return 2 * index + 1
  }

  getRightChildIndex(index) {
    return 2 * index + 2
  }

  hasParent(index) {
    return this.getParentIndex(index) >= 0
  }

  hasLeftChild(index) {
    return this.getLeftChildIndex(index) < this.heap.length
  }

  hasRightChild(index) {
    return this.getRightChildIndex(index) < this.heap.length
  }

  getParent(index) {
    return this.heap[this.getParentIndex(index)]
  }

  getLeftChild(index) {
    return this.heap[this.getLeftChildIndex(index)]
  }

  getRightChild(index) {
    return this.heap[this.getRightChildIndex(index)]
  }

  swap(index1, index2) {
    const temp = this.heap[index1]
    this.heap[index1] = this.heap[index2]
    this.heap[index2] = temp
  }

  peek() {
    if (this.heap.length === 0) {
      throw new Error("Heap is empty")
    }
    return this.heap[0]
  }

  poll() {
    if (this.heap.length === 0) {
      throw new Error("Heap is empty")
    }
    const item = this.heap[0]
    this.heap[0] = this.heap[this.heap.length - 1]
    this.heap.pop()
    this.heapifyDown()
    return item
  }

  add(item) {
    this.heap.push(item)
    this.heapifyUp()
  }

  heapifyUp() {
    let index = this.heap.length - 1
    while (this.hasParent(index) && this.getParent(index) > this.heap[index]) {
      this.swap(this.getParentIndex(index), index)
      index = this.getParentIndex(index)
    }
  }

  heapifyDown() {
    let index = 0
    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index)
      if (
        this.hasRightChild(index) &&
        this.getRightChild(index) < this.getLeftChild(index)
      ) {
        smallerChildIndex = this.getRightChildIndex(index)
      }
      if (this.heap[index] < this.heap[smallerChildIndex]) {
        break
      }
      this.swap(index, smallerChildIndex)
      index = smallerChildIndex
    }
  }
}

Here is an example of how you can use the MinHeap class to create a min heap tree:

const heap = new MinHeap()

heap.add(5)
heap.add(8)
heap.add(9)
heap.add(4)
heap.add(7)
heap.add(1)
heap.add(3)

console.log(heap.heap) // [1, 5, 3, 8, 7, 9, 4]

      1
    /   \
    5    3
  /   \  /  \
  8    7 9  4

To create a max heap, you can use the same class but change the comparison operator (<) in the heapifyDown function to > to ensure that the current node is swapped with the larger child.