Heaps and binary heaps.


Introduction to heaps:-

Heaps are the tree based data structures exactly like binary trees. Every heap is a binary tree. If both of them are the same then what is the difference between them?
The main difference lies between the arrangement of the child nodes. 

A point to remember while learning heaps is that “A heap is as compact as possible. All the child nodes for a node are completely filled first. But nodes are always filled from left to right.

Place the gif if possible.

Based on the arrangement of the child nodes there are 2 types of heaps. They are

  1. Max binary heaps.
  2. Min binary heaps.

1. Max binary heap:-

In max binary heaps arrangement of nodes is such that parent node is always greater than the child nodes. But we can not assure that which of the child node (left or right) is greater after the parent node. The same property must be recursively true for all sub-trees in that binary tree. 
 
One of the examples for the max binary heap is as follows.
Max-binary heap example
 

2. Min binary heap:-

A min binary heap is exactly opposite to the max binary heap. i.e parent node is always smaller than the child nodes. The same rule is recursively true for all the subtrees in the heap. 

One of the examples is as shown below.

Min binary heap example.
 

Representing binary heaps with arrays:-

Implementing a max or min binary heaps is very much similar to the implementations of the binary tree. It’s just that we have to make sure that the nodes are as compact as possible and must make sure that nodes are always filled from left to right.

 

Since we have already implemented it I will be using a list or array to implement a binary heap now. As a result of using Arrays, we should follow mathematical calculations to find out the child nodes of a parent at an index in the array. Observe the following max binary heap. 

using arrays to represent the binary heap.

By observing the above representation of max binary heap using arrays we can say the following.

using arrays to implement the binary heap.

Implementation of max and binary heaps are similar. It’s just that we check the greater value for the root node in max binary heap and smaller value for root node in min binary heap. I will be implementing the max binary heap here. Same process can be used for implementing the 

The base classes for the implementation of max binary heap are as follows.

public class MaxBinaryHeapWithList {
    ArrayList<Integer> values;
    public MaxBinaryHeapWithList() {
        super();
        this.values = new ArrayList<>();
    }
}
class MaxBinaryHeap {
    constructor() {
        this.values = [];
    }
}

Now that we know representing heaps with arrays, let’s implement some functionalities such as insert, remove etc.

1. Insert:-

Since we are using arrays to implement the heaps, insertion involves adding a new value to the array. Now to make sure that the inserted value doesn’t break the rules of max or min binary heaps we have to move it to the correct spot. This is nothing but bubbling up.
Following representation explains inserting the value 55 in to the max binary heap.
Heaps insert illustration.
The pseudocode for the insertion process is as shown below.
 heaps insert pseudocode.
max 
    public void insert(Integer value) {
        this.values.add(value);
        this.bubbleUp();
    }
    public void bubbleUp() {
        int index = this.values.size() - 1;
        int element = this.values.get(index);
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            int parent = this.values.get(parentIndex);
            if (element > parent) {
                this.values.set(parentIndex, element);
                this.values.set(index, parent);
                index = parentIndex;
            }
            else {
                break;
            }
        }
    }
    insert(element) {  
        this.values.push(element);
        this.bubbleUp();
    }
    bubbleUp() {
        let index = this.values.length - 1;
        const element = this.values[index];
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            let parent = this.values[parentIndex];
            if (element > parent) {
                this.values[parentIndex] = element;
                this.values[index] = parent;
                index = parentIndex;
            }
            else {
                break;
            }
        }
    }

2. Extract max:-
Extract max removes the maximum value from the max binary tree. Since we are removing an element from the list we have adjusted the remaining elements to follow the rules of the max binary tree. this process is called bubble down.

Heaps extract max illustration.
The pseudocode for the same is as follows.
extract max from the max binary heap.
public int extractRootElement() {
        int max = this.values.get(0);
        int end = this.values.get(this.values.size() - 1);
        if (this.values.size() > 0) {
            this.values.set(0, end);
            this.bubbleDown(0);
        }
        return max;
    }
    public void bubbleDown(int bubbleDownFromIndex) {
        int index = bubbleDownFromIndex;
        int length = this.values.size();
        int element = this.values.get(index);
        while (true) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int leftChild = 0, rightChild = 0;
            Integer swap = null;
            if (leftChildIndex < length) {
                leftChild = this.values.get(leftChildIndex);
                if (leftChild > element) {
                    swap = leftChildIndex;
                }
            }
            if (rightChildIndex < length) {
                rightChild = this.values.get(rightChildIndex);
                if (
                    (swap == null && rightChild > element) ||
                    (swap != null && rightChild > leftChild)) {
                    swap = rightChildIndex;
                }
            }
            if (swap == nullbreak;
            this.values.set(index, this.values.get(swap));
            this.values.set(swap, element);
            index = swap;
        }
        this.values.remove(length - 1);
    }
    extractRootElement() {
        var max = this.values[0];
        var end = this.values.pop();
        if (this.values.length > 0) {
            this.values[0] = end;
            this.bubbleDown(0);
        }
        return max;
    }
    bubbleDown(bubbleDownFromIndex) {
        var index = bubbleDownFromIndex;
        const length = this.values.length;
        const element = this.values[index];
        while (true) {
            var leftChildIndex = 2 * index + 1;
            var rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;
            if (leftChildIndex < length) {
                leftChild = this.values[leftChildIndex];
                if (leftChild > element) {
                    swap = leftChildIndex;
                }
            }
            if (rightChildIndex < length) {
                rightChild = this.values[rightChildIndex];
                rightChild = this.values[rightChildIndex];
                if (
                    (swap === null && rightChild > element) ||
                    (swap !== null && rightChild > leftChild)) {
                    swap = rightChildIndex;
                }
            }
            if (swap === nullbreak;
            this.values[index] = this.values[swap];
            this.values[swap] = element;
            index = swap;
        }
    }

Well, That’s it for now. Thanks for reading. Spread a word about learnovercoffee to your friends.