Heap

Heap

Introduction:

Heap is a tree-based data structure. It is a complete tree in which all of the nodes of the tree follow specific order. For example, if X is the parent of Y then the value of X follows a specific order with respect to the value of Y.

In the context of a binary min-heap, it means that:

• Except leaf nodes, every node will have exactly two children nodes.
• For each node X its value will be less than its children.

Insertion of item in the Heap:

Let's say we already have a binary min-heap with N items in it and we want to add one more item in it, say X. Wt will stick with the order of filling the leaf level from left to right - to keep satisfying the constraint that a heap is a complete tree.

Now to check if the heap order is still preserved after insertion, we need to compare X's value with its parent say Y. In the context of a binary min-heap, if value of X is:

• greater than its parent node then heap order is still preserved because Y still is less than both its children. And since we inserted X at the leaf level it doesn't have any children and is a valid heap node at the leaf level.
• less than its parent node then heap order is not preserved because Y should be less than both of its children X' and X but here X is less than Y.

To restore the heap order, what can we do? If look at X, its parent Y and its sibiling X' then we can re-arrange that particular sub-tree with X as the new parent node and keep X' where it was and Y in place of X.

Now the heap order is preserved in this new sub-tree, why? Since Y was already smaller than X' and X is smaller than Y, X is also smaller than X' (X < Y and Y < X' hence X < X')

But because of this swapping we may have violated the heap order, why? Let's say the parent of Y was Y' and Y's sibiling was Z' and now Y' has two children Z' and X. If X > Y' then heap order is preserved for Y' but if it X < Y' then the heap order is not preserved. We need to swap Y' and X again to restore the heap order.

This can go on till we find a parent which is smaller than X or X can end up replacing the root if it is the smallest element in the heap till now.

So, the insertion can take up to O(logN) in the worst-case when we insert a minimum element in the min-heap.

💡 As a side note, it is worth noting that we will need access to the parent node whenever we insert any element in the heap

• for checking if the heap order is preserved or not and
• for the above swapping process in case heap order is not preserved and to correct the heap order

Deletion of root from the Heap:

Let's say we want to remove the root from the min-heap with N items in it. Since our heap previously was satisfying the constraint of being a complete binary tree and we always inserted items from left to right in the leaf level, after the removal of the root we can pluck the rightmost element from the leaf and make it the new root. This way, we can ensure that the new structure after the removal of the root will still form a complete tree, but the heap order may not be preserved.

We now have to re-arrange the heap so that the heap order is preserved. For this we can do something as follows: Consider the new root as R' and old children of R X (left) and Y (right). We can do two things at this point:

• If X < Y then we can make X the new root of the heap, keep Y as the right children and R' as the left children. This will ensure that the right sub-tree of new root follows min-heap properties and we just need to focus on fixing the left sub-tree of the new root.
• If Y < X then we can make Y the new root of the heap, keep X as the left children and R' as the new right children. This will ensure that the left sub-tree of new root follows min-heap properties and we just need to focus on fixing the right sub-tree of the new root.

Recursively, we can keep doing this for each level until we find a proper place for the R' to settle, pruning the whole left and right sub-tree as we go down and doing this re-arrangement in logarithmic time. In hindsight, plucking the rightmost element from leaf level was the best choice because it allowed us to retain the old min-heap as a complete tree.

Internal data structure:

As we saw in the insertion process, we need to get the reference to the parent node from a child node. If we are using a non-linear data strcture then we will need to keep a pointer to the parent node from a child node.

Also, as we saw in the deletion process, we need to find the rightmost element in the leaf level. If we are using a non-linear data strcture finding this can be a little cumbersome.

So, instead of using a non-linear data structure to model the tree, we use array to store the elements in a tree like fashion.

If we are dealing with binary heaps then we know from the complete tree property that there will be:

• 1 element on the first level
• 2 elements on the second level
• 4 elements on the third level
• 2^k elements on the (k + 1)th level

and so on and so forth.

The above pattern can be flattened into an array as follows:

• Range [0, 0] will be the first level
• [1, 2] will be the second level
• [3, 6] will be the third level
• [2^k - 1, 2^(k + 1) - 2] will be the (k + 1)th the level in general

So the benefits of using the array over non-linear data strcture would be:

• Appending the element in the end will ensure that we are always filling the leaf level from left to right fashion. This also ensures that:
  • If you're at index i then your left child will be at index 2 * i + 1 and the right child will be at index 2 * i + 2.
  • If you're not already at the root (i === 0) you can look up your parent by checking arr[(i - 1) / 2].
  • arr[lastElementIndex] will give you the rightmost element in the leaf whenever we are removing root node from the heap.

Copycopy code to clipboard
1type Comparator<T = any> = (
2  a: { value: T; priority: number },
3  b: { value: T; priority: number }
4) => number;
5
6const minHeapComparator = <T = any>(
7  a: { value: T; priority: number },
8  b: { value: T; priority: number }
9) => a.priority - b.priority;
10
11class Heap<T = any> {
12  private heap: Array<{ value: T; priority: number }>;
13  private lastElementIndex: number;
14  private comparator: Comparator<T>;
15
16  static getParentIndex(index: number) {
17    return Math.floor((index - 1) / 2);
18  }
19
20  static getLeftChildIndex(index: number) {
21    return 2 * index + 1;
22  }
23
24  static getRightChildIndex(index: number) {
25    return 2 * index + 2;
26  }
27
28  private getLeftChild(index: number) {
29    const leftChildIndex = Heap.getLeftChildIndex(index);
30    return this.heap[leftChildIndex];
31  }
32
33  private getRightChild(index: number) {
34    const rightChildIndex = Heap.getRightChildIndex(index);
35    return this.heap[rightChildIndex];
36  }
37
38  constructor(comparator: Comparator<T> = minHeapComparator) {
39    this.heap = [];
40    this.lastElementIndex = -1;
41    this.comparator = comparator;
42  }
43
44  insertWithPriority(val: { value: T; priority: number }) {
45    this.heap.push(val);
46    this.lastElementIndex++;
47
48    // Compare with the parent and keep swapping until found a perfect place
49    let currentIndex = this.lastElementIndex;
50    let parentIndex = Heap.getParentIndex(currentIndex);
51
52    // currentNode is to be placed above parentNode
53    while (
54      currentIndex &&
55      this.comparator(this.heap[currentIndex], this.heap[parentIndex]) < 0
56    ) {
57      const temp = this.heap[parentIndex];
58      this.heap[parentIndex] = this.heap[currentIndex];
59      this.heap[currentIndex] = temp;
60
61      currentIndex = parentIndex;
62      parentIndex = Heap.getParentIndex(currentIndex);
63    }
64  }
65
66  heapifyDown(): T | null {
67    let currentIndex = 0;
68
69    let currentNode = this.heap[currentIndex];
70    let leftChild = this.getLeftChild(currentIndex);
71    let rightChild = this.getRightChild(currentIndex);
72
73    while (leftChild) {
74      let leftChildIndex = Heap.getLeftChildIndex(currentIndex);
75      let rightChildIndex = Heap.getRightChildIndex(currentIndex);
76
77      let smallerChildIndex = leftChildIndex;
78      let smallerChildNode = leftChild;
79
80      // rightChild's priority is less than leftChild's priority
81      if (rightChild && this.comparator(rightChild, leftChild) < 0) {
82        smallerChildIndex = rightChildIndex;
83        smallerChildNode = rightChild;
84      }
85
86      // currentNode's priority is less than its smaller child
87      // Heap order is preserved, no need to do anything beyond this
88      if (this.comparator(currentNode, smallerChildNode) < 0) break;
89
90      // Swap currentIndex with smallerOne
91      this.heap[currentIndex] = smallerChildNode;
92      this.heap[smallerChildIndex] = currentNode;
93
94      // Update loop variables
95      currentIndex = smallerChildIndex;
96      leftChild = this.getLeftChild(currentIndex);
97      rightChild = this.getRightChild(currentIndex);
98    }
99  }
100
101  removeRoot(): T | null {
102    const lastElement = this.heap.pop();
103    if (!lastElement) return null;
104
105    this.lastElementIndex -= 1;
106    if (this.heap.length === 0) return lastElement.value;
107
108    const rootElement = this.heap[0];
109
110    // Bring the right-most element (last element) to the root
111    this.heap[0] = lastElement;
112    this.heapifyDown();
113
114    return rootElement.value;
115  }
116
117  peek(): T | null {
118    return this.heap[0] ? this.heap[0].value : null;
119  }
120
121  size(): number {
122    return this.heap.length;
123  }
124
125  print() {
126    console.log(JSON.stringify(this.heap, null, 2));
127  }
128}
129
130const heap = new Heap<string>();
131
132heap.insertWithPriority({ value: "Lorem", priority: 3 });
133heap.insertWithPriority({ value: "Ipsum", priority: 2 });
134heap.insertWithPriority({ value: "Dolor", priority: 1 });
135heap.insertWithPriority({ value: "Sit", priority: 0 });
136heap.insertWithPriority({ value: "Amet", priority: 4 });
137
138heap.print();
139
140console.log(heap.removeRoot());
141console.log(heap.removeRoot());
142console.log(heap.removeRoot());
143console.log(heap.removeRoot());
144console.log(heap.removeRoot());
145console.log(heap.removeRoot());
146
147heap.print();

Heap based questions:

Top k frequent elements

Problem Statement:

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Solution:

We can use MaxHeap here. We will put each element from nums array and we will use its frequency as the priority for the MaxHeap.

This way, we will be have most frequent element at the root of the MaxHeap and when we remove from the MaxHeap first time. When we remove the element again from the MaxHeap, we will get the second most frequent element. We can perform the remove operation k times and we will end up with the top k frequent elements.

💡 We don't necessarily have to use MaxHeap here. We can use the MinHeap here as well and assign negative of the frequency as the priority. This way, the element with the highest frequency will have the lowest priority and it will be at the root of the heap when we perform remove operation in the MinHeap.

The code for the solution of this problem with MinHeap can be found here.

Merge k Sorted Lists

Problem Statement:

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Solution:

First of all, we start by creating a dummy node for the merged list - mergedListHead. We also keep a pointer lastInsertedNode and initialise it with mergedListHead.

Then we put all the heads of the lists in a MinHeap where each node's priority will be decided by that particualr node's value.

Then, we iterate till our heap does not get empty. In each iteration, we remove the lowest priority element from heap. We make our lastInsertedNode point to this minimum value node. We update our lastInsertedNode and we then add the removed node's next node to keep things moving.

Time complexity: O(klogk) to first make the heap.

Explanation: Since we are removing the minimum element out of k elements in the heap in each iteration, it will take O(logk) time. We also put an item in the heap after removal which will take O(logk) time. And we are doing this for all of the N elements so overall it will take O(Nlogk) time.

The code for the above approach can be found here.