Abdullah Al Hommada blog

Heap algorithms are a set of algorithms that are based on the heap data structure. A heap is a binary tree where the parent node has a value greater than or equal to its children in a Max Heap, or the parent node has a value less than or equal to its children in a Min Heap. Heap algorithms can be used for sorting, searching, and data manipulation.

Here are examples of Heap algorithms implemented in JavaScript:

Heap Sort: Heap Sort is a sorting algorithm that uses the heap data structure to sort an array in ascending or descending order. In a Max Heap, the largest element is always at the root of the heap, so we can repeatedly remove the root and place it at the end of the array until the heap is empty. The resulting array will be sorted in descending order. Here's an implementation of Heap Sort in JavaScript:

function heapSort(array) {
  let len = array.length;

for (let i = Math.floor(len / 2); i >= 0; i--) {
heapify(array, i, len);
}

for (let i = len - 1; i > 0; i--) {
[array[0], array[i]] = [array[i], array[0]];
heapify(array, 0, i);
}

return array;
}

function heapify(array, i, len) {
let largest = i;
let left = 2 _ i + 1;
let right = 2 _ i + 2;

if (left < len && array[left] > array[largest]) {
largest = left;
}

if (right < len && array[right] > array[largest]) {
largest = right;
}

if (largest !== i) {
[array[i], array[largest]] = [array[largest], array[i]];
heapify(array, largest, len);
}
}

Priority Queue: A priority queue is a data structure that allows us to insert elements with a priority and remove the element with the highest priority. A priority queue can be implemented using a heap, where the highest priority element is always at the root of the heap. Here's an implementation of a priority queue in JavaScript:

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

  insert(value, priority) {
    this.heap.push({ value, priority });
    let index = this.heap.length - 1;

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);

      if (this.heap[parentIndex].priority > this.heap[index].priority) {
        break;
      }

      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  remove() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop().value;
    }

    let maxValue = this.heap[0].value;
    this.heap[0] = this.heap.pop();
    let index = 0;

    while (true) {
      let leftIndex = 2 * index + 1;
      let rightIndex = 2 * index + 2;

      if (leftIndex >= this.heap.length) {
        break;
      }

      let maxChildIndex = leftIndex;

      if (rightIndex < this.heap.length && this.heap[rightIndex].priority > this.heap[leftIndex].priority) {
        maxChildIndex = rightIndex;
      }

      if (this.heap[index].priority >= this.heap[maxChildIndex].priority) {

Heap Algorithm and data structure with examples