What is a Priority Heap?

A priority heap is a bit like a family tree, except each person (or piece of data) has a priority number attached to them. The higher the number, the more important they are. The most important person always sits at the top of the tree, and their children (the data below them) are less important.

How Does It Work?

Priority heaps have a few special tricks:

  • Add: You can add a new person to the tree, and they'll automatically find their right place based on their priority.
  • Peek: You can quickly see who the most important person is without removing them from the tree.
  • Remove: You can take the most important person off the top of the tree, and everyone else will shuffle around to keep the tree organized.

When Should You Use a Priority Heap?

  • Whenever you need to keep track of the most important things in a group.
  • In situations where you often need to add new things or remove the top priority item.

Implementation (JS)

class MinHeap {
  constructor() {
    this.heap = []
  }
 
  peak() {
    if (this.heap.length === 0) return null
    return this.heap[0]
  }
 
  add(value) {
    this.heap.push(value)
    this.heapifyUp()
  }
 
  remove() {
    if (this.heap.length === 0) {
      return null
    }
    const item = this.heap[0]
    this.heap[0] = this.heap[this.heap.length - 1]
    this.heap.pop()
    this.heapifyDown()
    return item
  }
 
  heapify(list) {
    for (let index = 0; index < list.length; index++) {
      this.add(list[index])
    }
  }
 
  heapifyUp() {
    let index = this.heap.length - 1
 
    while (true) {
      // get parent
      const parentIndex = Math.floor((index - 1) / 2)
      if (!this.heap[parentIndex]) return
      if (this.heap[parentIndex] > this.heap[index]) {
        // swap
        const temp = this.heap[parentIndex]
        this.heap[parentIndex] = this.heap[index]
        this.heap[index] = temp
        // heapify parent
        index = parentIndex
      } else {
        return
      }
    }
  }
 
  heapifyDown() {
    let index = 0
    while (true) {
      const leftChild = index * 2 + 1
      const rightChild = index * 2 + 2
 
      if (!this.heap[leftChild] && !this.heap[rightChild]) return
 
      let minIndex = leftChild
      if (this.heap[rightChild] && this.heap[leftChild] > this.heap[rightChild]) {
        minIndex = rightChild
      }
 
      if (this.heap[index] > this.heap[minIndex]) {
        // swap
        const temp = this.heap[minIndex]
        this.heap[minIndex] = this.heap[index]
        this.heap[index] = temp
 
        // heapify min Child
        index = minIndex
      } else {
        return
      }
    }
  }
}
class MinHeap {
  constructor() {
    this.heap = []
  }
 
  peak() {
    if (this.heap.length === 0) return null
    return this.heap[0]
  }
 
  add(value) {
    this.heap.push(value)
    this.heapifyUp()
  }
 
  remove() {
    if (this.heap.length === 0) {
      return null
    }
    const item = this.heap[0]
    this.heap[0] = this.heap[this.heap.length - 1]
    this.heap.pop()
    this.heapifyDown()
    return item
  }
 
  heapify(list) {
    for (let index = 0; index < list.length; index++) {
      this.add(list[index])
    }
  }
 
  heapifyUp() {
    let index = this.heap.length - 1
 
    while (true) {
      // get parent
      const parentIndex = Math.floor((index - 1) / 2)
      if (!this.heap[parentIndex]) return
      if (this.heap[parentIndex] > this.heap[index]) {
        // swap
        const temp = this.heap[parentIndex]
        this.heap[parentIndex] = this.heap[index]
        this.heap[index] = temp
        // heapify parent
        index = parentIndex
      } else {
        return
      }
    }
  }
 
  heapifyDown() {
    let index = 0
    while (true) {
      const leftChild = index * 2 + 1
      const rightChild = index * 2 + 2
 
      if (!this.heap[leftChild] && !this.heap[rightChild]) return
 
      let minIndex = leftChild
      if (this.heap[rightChild] && this.heap[leftChild] > this.heap[rightChild]) {
        minIndex = rightChild
      }
 
      if (this.heap[index] > this.heap[minIndex]) {
        // swap
        const temp = this.heap[minIndex]
        this.heap[minIndex] = this.heap[index]
        this.heap[index] = temp
 
        // heapify min Child
        index = minIndex
      } else {
        return
      }
    }
  }
}