Heaps & Priority Queues

The heart of Graph Algorithms.

Prerequisites:

1. Knowledge of structure and objects (only to understand the code).

What will we learn?

1. Representing trees in an array.
2. Hashing (general concept).
3. Concepts of Heap.

What is a Priority Queue and why do we need a heap to implement it?

Priority Queue is as the name suggests when a queue is maintained while considering priorities of the elements in it. Highly used in graph algorithms where choosing the next best path is the key.

Naively the priority queue can be handled in two ways:

1. Inserting the new element at a suitable position in the queue and moving the rest.
2. Pop the suitable one from the queue and then move the rest.

In both the cases, the complexity is O(N) but by using a Heap data structure we can reduce this complexity to O(log N), this is a significant improvement and hence becomes important for us to study and know about.

Heap is nothing but a binary tree with some extra properties associated with it, the rules for a binary tree to qualify for a heap are:

1. The tree should be a complete binary tree.
2. The element contained by each node is smaller than or equal to the elements of that node’s children (in case of a Min-Heap).

Array Representation of Trees

We will be using trees in our approach to build a priority queue, an easy implementation of trees is by using arrays to represent them. Let’s see how this is done.

Array representation of a tree

Top-to-Bottom, Left-to-Right number them sequentially starting from 0, thus formed sequence is called the array representation of the tree.

From a simple observation you can deduct following properties:
->left-child of i = 2*i+1
->right-child of i = 2*i+2
->parent of i = (i-1)/2

with these arrow in your quiver, you’re all set to work with trees.

Hashing (Basics)

Hashing comprises of converting some property of the object to a value that is easier to map i.e. search. For example, if you have N strings and you need to find the frequency of each of them.

we can hash the string as:

H(S)= (s[0] + s[1] . P + s[2] . P² + …. + s[n-1] . P^(n-1)) mod m

It is called a polynomial rolling hash function, for alphabets, where P is a prime and m is a large prime. P = 53 and M = 10⁹+7 are possible choices.

This function effectively converts a string into a value which is easy to search and account for, everytime you encounter a string convert it into its hash and increment the count for that value.

Note: The hash functions are prone to collisions (multiple strings can return same value, in such case chaining is used, which is not covered in this section)

Operations involved in a Heap

Key points:

1. The height of a binary tree with n nodes is Log N
2. After an operation, if properties of the heap are violated we need to fix it.

Do not worry if you don’t understand the following operations the first time, just read them twice and buckle up.

Operations:

1. getMin(): It returns the root element of MinHeap. Time Complexity of this operation is O(1).
2. extractMin(): Removes the minimum element from MinHeap. Time Complexity of this Operation is O(Log N) as this operation needs to maintain the heap property (by calling heapify()) after removing root.
3. decreaseKey(): Decreases value of key. The time complexity of this operation is O(Log N). If the decreases key value of a node is greater than the parent of the node, then we don’t need to do anything. Otherwise, we need to traverse up to fix the violated heap property.
4. insert(): Inserting a new key takes O(Log N) time.
5. delete(): Deleting a key also takes O(Log N) time. We replace the key to be deleted with minimum infinite by calling decreaseKey(). After decreaseKey(), the minus infinite value must reach root, so we call extractMin() to remove the key.

Let us understand the operations

Note: Hashing is used to map nodes(structure objects) to a value, it is these hashed values in the tree and not the priorities themselves.

In the diagrams, the value inside the node depicts the priority of the node

1. Insert Operation :

Let's insert a 4 in the heap

After insertion, you can observe that the property of the heap is violated and thus we need to fix it, we do this by traversing the value upwards.

This requires two steps swap(13, 4) and then swap(5, 4). We do not swap anymore because 3 is smaller than 4

2. Function Heapify

When the root is extracted by extractMin() function, we replace root by the last element and then function heapify pushes this element downwards until all the heap properties are satisfied.

extractMin() would return 3 and is replaced by 13 to make the tree a complete binary tree.

however now the other property is violated, 13 is greater than 4 and 7, to fix this we choose the lowest of two children and replace it from the parent.

we keep doing this until 13 is smaller than both its child nodes.

Every time you call the function extractMin() the element with the lowest priority in case of minHeap and highest priority in case of maxHeap is returned in O(log N) and O(N).

Lets Code it up

#include<iostream>
using namespace std;
// Each node of the tree
struct Node {
    int key, priority;
    Node () {}
    Node (int key, int priority) {
        this->key = key;
        this->priority = priority;
    }
};
struct MinHeap {
    int size;
    // The tree of nodes in its array representation
    Node *node;
    int *map;
    MinHeap (int capacity = 100000) {
        map = new int[capacity];
        node = new Node[capacity];
        size=0;
    }
    int parent(int i) {
        return (i-1)/2;
    }
    int leftchild(int i) {
        return i*2+1;
    }
    int rightchild(int i) {
        return i*2+2;
    }
    // hashing the node using its key
    // you can customize this by yourself
    int hash(Node node) {
        return node.key * 31;
    }
    void heapify(int i) {
        int small = i;
        int l = leftchild(i);
        int r = rightchild(i);
        if(l < size && node[l].priority < node[small].priority)
            small=l;
        if(r < size && node[r].priority < node[small].priority)
            small=r;
        if(small!=i) {
            swap(map[hash(node[small])], map[hash(node[i])]);
            swap(node[small], node[i]);
            i=small;
            heapify(i);
        }
    }
    int getMin() {
        return node[0].key;
    }
    void insert(int key, int priority) {
        int i = size++;
        node[i] = Node(key, priority);
        map[hash(node[i])] = i;
        while (i!=0 && node[parent(i)].priority>node[i].priority) { 
            swap(map[hash(node[i])], map[hash(node[parent(i)])]);
            swap(node[i], node[parent(i)]);
            i = parent(i);
        }
    }
    void decrease(int key, int newPriority) {
        int i = map[hash(Node(key, newPriority))];
        node[i].priority = newPriority;
        
        while (i!=0 && node[parent(i)].priority>node[i].priority) { 
            swap(map[hash(node[i])], map[hash(node[parent(i)])]);
            swap(node[i], node[parent(i)]);
            i = parent(i);
        }       
    }
    int extractmin() {
        Node root = node[0]; 
        node[0] = node[size-1]; 
        size--; 
        heapify(0);
        return root.key;
    }
    void deleteKey(int key) { 
        decrease(key, -1000); 
        extractmin();
    }
    bool empty() {
        return size<=0;
    }
};
int main() { 
    MinHeap h; 
    h.insert(3, 4); 
    h.insert(2, 3); 
    h.insert(15, 5); 
    h.insert(5, 2); 
    h.insert(4, 1); 
    h.insert(45, 2); 
    cout<<h.extractmin()<<endl;
    cout<<h.getMin()<<endl;
    h.decrease(2, 1);
    cout << h.getMin()<<endl; 
    while(!h.empty())
        cout<<".."<<h.extractmin()<<endl;
    return 0; 
}

Reference:

Binary Heap — GeeksforGeeks

String Hashing — Competitive Programming Algorithms