Class MinPriorityQueue

Data-Structures/Heap/MinPriorityQueue.js:13–125

// Functions: insert, delete, peek, isEmpty, print, heapSort, sink

class MinPriorityQueue {
  // calls the constructor and initializes the capacity
  constructor(c) {
    this.heap = []
    this.capacity = c
    this.size = 0
  }

  // inserts the key at the end and rearranges it
  // so that the binary heap is in appropriate order
  insert(key) {
    if (this.isFull()) return
    this.heap[this.size + 1] = key
    let k = this.size + 1
    while (k > 1) {
      if (this.heap[k] < this.heap[Math.floor(k / 2)]) {
        const temp = this.heap[k]
        this.heap[k] = this.heap[Math.floor(k / 2)]
        this.heap[Math.floor(k / 2)] = temp
      }
      k = Math.floor(k / 2)
    }
    this.size++
  }

  // returns the highest priority value
  peek() {
    return this.heap[1]
  }

  // returns boolean value whether the heap is empty or not
  isEmpty() {
    return this.size === 0
  }

  // returns boolean value whether the heap is full or not
  isFull() {
    return this.size === this.capacity
  }

  // prints the heap
  print(output = (value) => console.log(value)) {
    output(this.heap.slice(1))
  }

  // heap reverse can be done by performing swapping the first
  // element with the last, removing the last element to
  // new array and calling sink function.
  heapReverse() {
    const heapSort = []
    while (this.size > 0) {
      // swap first element with last element
      ;[this.heap[1], this.heap[this.size]] = [
        this.heap[this.size],
        this.heap[1]
      ]
      heapSort.push(this.heap.pop())
      this.size--