Heap

Today we'll talk about heaps which are similar to trees where each parent node value is greater than its childrens. There are two types of heaps maxHeaps and minHeaps as the name suggests max heap goes from highest to lowest value and min heap goes from lowest to greatest.

Theory

The heap structure is an abstract concept, their implementation relies on a simple array. Now you might ask, if we rely on arrays how do we know which one is the parent and which ones are their child's.

Well it's an array where order matters, the root is obviously the first node and it's child are the following ones.

For simplicity sake we will take binary heaps so that we have at most 2 childs, if we are looking for the childs of the root node we would look at index 1 and 2. Ok now what if we want to look for the childs of node at index 42 ?

Find the child's index

Well we need a way to find the childrens solely based on the parent's index (where n is the index):

• left child : 2n + 1
• right child : 2n + 2 So for node at index 0 it would be:
• 2 * 0 + 1 = 1
• 2 * 0 + 2 = 2 And for node at index 42 it would be:
• 2 * 42 + 1 = 85
• 2 * 42 + 2 = 86

Find the parent's index

Now what about the parent: (n - 1) / 2 (where n is the index) So if we look at the parent of index 1 : (1 - 1) / 2 = 0 If we now look a the parent of index 6 : (6 - 1) / 2 = 2.5

For this exact use case we need to floor the result so that we always get the right index : Math.floor((index - 1) / 2)

Implementation

Heap Class

The Heap class represents our custom data structure which is actually simply an array.

class maxBinaryHeap {
  constructor() {
    this.values = [];
  }
}

Insert

Insert a new value into the heap.

function insert(value) {
  this.values.push(value);
  let index = this.values.length - 1;
  const element = this.values[index];
  while (true) {
    const parentIndex = Math.floor((index - 1) / 2);
    const parent = this.values[parentIndex];
    if (parent >= element) break;
    this.values[parentIndex] = element;
    this.values[index] = parent;
    index = parentIndex;
  }
}
const heap = [45, 36, 38, 24, 5];
heap.insert(12); // [45, 36, 38, 24, 5, 12]
heap.insert(56); // [56, 36, 45, 24, 5, 12, 38]

Explanation: Here we need what we call bubbling, we essentially add the new value to the end of the array before bubbling the value up (comparing and replacing with its parent as long as the parent is smaller that the value):

• Push the new value at the end of the array
• Define two variables, the index at which we start (the end) and the element at this position (the one we just added).
• Find the parentIndex and retrieve its value
• Loop as long as the parent value is greater than the element we added.
• If we didn't break it means our parent is smaller than the inserted value, we can swap
• we set the index to be the parentIndex has it now is the index our new value is currently at.

Extraction

ExtractMax or (extractMin depending on the heap's type). Which as the name suggests is used to pop the head of the tree before replacing it with the biggest value, for this we will need bubbling again.

function extractMax() {
  let index = 0;
  const head = this.values[index];
  const end = this.values.pop();
  if (!this.values.length) return head;
  const length = this.values.length;
  this.values[0] = end;
  const element = this.values[index];
  while (true) {
    const leftIndex = 2 * index + 1;
    const rightIndex = 2 * index + 2;
    let left = null;
    let right = null;
    let swap = null;

    if (leftIndex < length) {
      left = this.values[leftIndex];
      if (left > element) {
        swap = leftIndex;
      }
    }
    if (rightIndex < length) {
      right = this.values[rightIndex];
      if (
        (swap === null && right > element) ||
        (swap !== null && right > left)
      ) {
        swap = rightIndex;
      }
    }
    if (swap === null) break;
    this.values[index] = this.values[swap];
    this.values[swap] = element;
    index = swap;
  }
  return head;
}

Explanation:

• we define four variables: the length which will be used to check if our iterations gets us out of bound, the index at which we start, the head, the end the last item and the element just represent the new head (after the pop).
• Before going further we check if there are any items in the heap if not we simply return.
• Otherwise we swap our first value with the last so that we can start bubbling from there.
• We loop until we have nothing left to swap
• Inside the loop we define a few variables the left child index, the right side index based on the current index.
• Then another few variables starting at null which will be filled on each iterations. First the left value which holds the left child of the current element we are looking at then the right child and a swap which will hold the value to swap.
• Now for the left child we check is it actually greater than the current element if so we store it in the swap variable.
• For the right value it's a bit harder, we basically have to check if either there is no swap but the right is greater than the current element or if there is a swap but our right value is greater than it.
• If one of those conditions match set swap to be our right value.
• Now we should have a swap value if not it simply means that there is no value greater than our current head so we can just stop there.
• If we do have a swap value well then we simply swap the current index with the swap index and we update the index to be the swap index so we can keep on comparing down the heap.

Let break the result down:

const heap = [56, 36, 45, 24, 5, 12];
heap.extractMax();
// 1. [56, 36, 45, 24, 5]
// 2. [12, 36, 45, 24, 5]
// 3. [45, 36, 12, 24, 5]
// 4. [45, 36, 24, 12, 5]
// Return 56

So here we have it our head is successfully removed and returned and our tree is successfully reordered.

Practical Use Cases

Now that we know what a heap looks like when should we use it? Well heaps are a great data structure for real world scenarios that involves prioritizing.

• TODO list: Heaps allow use to order task by priority and extract the one with the highest priority
• Processes: Heaps are also used as computer process to handle the execution priority

Let's see from our heap how we can take it one step further and build a priority queue from it:

Priority queue

Same as before we have our priority queue class we a simple array:

PriorityQueue Class

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

Node Class

Now to handle more than a simple value we have nodes which hold a value and a priority which could hold a value from 1 to 5 where 1 is the highest for example.

class Node {
  constructor(value, priority) {
    this.value = value;
    this.priority = priority;
  }
}

Insert

Same function as before but now instead of comparing the element itself we compare by priority:

function insert(value, priority) {
  const newNode = new Node(value, priority);
  this.values.push(newNode);
  let index = this.values.length - 1;
  const element = this.values[index];

  while (true) {
    const parentIndex = Math.floor((index - 1) / 2);
    const parent = this.values[parentIndex];
    if (parent.priority >= element.priority) break;
    this.values[parentIndex] = element;
    this.values[index] = parent;
    index = parentIndex;
  }
}

const heap = [45, 36, 38, 24, 5];
heap.insert(12); // [45, 36, 38, 24, 5, 12]
heap.insert(56); // [56, 36, 45, 24, 5, 12, 38]

ExtractMax

Same here, we compare by the priority property instead of the value itself:

function extractMax() {
  let index = 0;
  const head = this.values[index];
  const end = this.values.pop();
  if (!this.values.length) return head;
  const length = this.values.length;
  const element = this.values[index];
  this.values[index] = end;
  while (true) {
    const leftIndex = 2 * index + 1;
    const rightIndex = 2 * index + 2;
    let left = null;
    let right = null;
    let swap = null;
    if (leftIndex < length) {
      left = this.values[leftIndex];
      if (left.priority > element.priority) {
        swap = leftIndex;
      }
    }

    if (rightIndex < length) {
      right = this.values[rightIndex];
      if (
        (swap === null && right.priority > element.priority) ||
        (swap !== null && right.priority > left.priority)
      ) {
        swap = rightIndex;
      }
    }

    if (swap === null) break;
    this.values[index] = this.values[swap];
    this.values[swap] = element;
    index = swap;
  }

  return head;
}

Let's say we are building a todo list where each element has a priority ranging from 1 to 5 with 5 being the highest priority.

const priority_queue = new PriorityQueue();
priority_queue.insert("work", 5);
priority_queue.insert("sport", 4);
priority_queue.insert("laundry", 5);
const firstTodo = priority_queue.extractMax();
// {value: "work", priority: 5}
const secondTodo = priority_queue.extractMax();
// {value: "laundry", priority: 5}
// "sport"
priority_queue.insert("grocery", 5);
// "grocery"
// "sport"

So there we have a fully functional Todo list thanks to our priority queue data structure. Note that the logic here relies on the highest priority but it could also be the lowest or any other value you choose.

Performance Considerations

Now that we know when do use it, why do we use it? Well because they are really fast at insertion and deletion and when I say really fast I mean bigO(log N) which is really performant as constant time is almost impossible unless sacrifying space complexity. Why? Because when we reorder the tree (or heapify) we only have to check once for every level. If we for example take a binary heap with 16 elements we only have 4 comparison to make, 1 for every level.

• Time Complexity: For insertion, extract operation, the average time complexity is O(log n) for a balanced BST. However, in the worst case (unbalanced tree), it can degrade to O(n).
• Space Complexity: The space complexity for traversal methods is O(n) due to the storage required for the result array and the call stack or queue.

Conclusion

So that's it for heaps, I hope you now understand when and how to use them, if you have any questions or clarifications please leave a comment I might learn something from you as well!

Happy coding!