Binary Heap In C#

Binary Heap?

 

Binary heap is a Binary tree with some special properties.

 

Heap Properties are:

• Min Heap : parent node value is less than child node value
• Max Heap : Parent node value is greater than child node value.

Example of min and max heap in pictorial representation.

 

Why do we need Binary Heap?

 

Let us consider array data structure as an example. When we want to insert an element inside the sorted array, we need to find "Min/Max" element and insert in a proper position. We also need to make sure that the inserted new element will not affect the current element or size of the array. This implementation takes O(log n) time for smaller array size. In the worst-case this takes O(n) time

 

Let us consider one more example. We need to insert an element in a linked list. As you are already aware, insertion in linked list will take O(n) time, and also we need to make sure new element is inserted in the proper position.

 

This is where Binary heap comes into the picture. In binary heap in the first level we will find out that parent node is greater/lesser than child node. So the insertion of elements is easy. Inserting the element at the proper position takes no more than O(log n) time.

 

Practical Usage of Heap 

1. Prims algorithm
2. Heap sort
3. Priority Queue

Implementation of Heap 

 

We can implement the Binary heap in two ways,

• Array based implementation
• Linked list based implementation : Asits implementation takes O(n) time, we will not be using it in this article.

Array based implementation,

 

Create a blank binary heap

 

Step 1

 

CreateHeap(size)--------O(1)

 

Step 2

 

Initialize the Size of the array [Size+1] ----O(1) // Since you know that in tree implementation array element insertion starts from 1st position.

Time Complexity: O(1)

Space Complexity: O(n)/// Heap is created.

 

Let us write a code for above algorithm 

Public Class BinaryHeapExample{

    int[] arr;
   int  sizeOfTree;
     // Create a constructor
   public BinaryHeapExample(int size){
     //We are adding size+1, because array index 0 will be blank.
      int arr = new int[size+1];
     this.sizeofTree=0;
     Console.WriteLine("Empty heap has been created Successfully");
    }
 }

Peek of Heap

 

Peek is nothing but the root of the heap. To get the value of peek of the heap:

 

Algorithm

 

Step1: PeekofHeap() ---------------------------------O(1)

Step2: if(peek is null)----------------------------------O(1)

Step3: return error------------------------------------O(1)

Step4: else

Step5: return first cell of the array.----------------O(1)

Time Complexity : O(1)

Space Complexity : O(1)

public int PeekOfHeap()
{
   if(SizeOfTree == 0)
      return 0;
   else
      return arr[1];
}

To get the Size of the Heap

 

Here we are not returning the size of the array, we are returning the size of the heap.

 

Algorithm

 

Step 1: SizeofHeap()-------------O(1)

Step 2: return sizeofTree--------O(1)

Time Complexity : O(1)

Space Complexity : O(1)

public int SizeOfHeap(){

   Console.WriteLine("The size of the heap is:"+ SizeOfTree);
  return SizeOfTree;
}

Insertion in Binary heap

 

Before inserting the element in Binary heap, we need to validate some of the edge cases.

1. We need to find the empty cell first
2. Then we need to check if the min and max property of the node is maintained
3. If not maintained we need to swap the elements.

Let us consider an example. 

 

After inserting "1" in the above heap, the min and max property of the heap is distorted. Now we need to do the swapping of the elements in the above heap.

1. 19>1 : swap 1 and 19
2. 5> 1: swap 1 and 5
3. 3> 1: swap 1 and 3.

After swapping "1" becomes the root node. Find the tree below after swapping. We need to swap the elements from "Bottom to Top"

Algorithm for Insertion in Heap,

 

Step 1: InsertValueInHeap(value)-----------------------------------------O(1)

Step 2: if(SizeofTree is null) return error---------------------------------O(1)

Step 3: else, find empty cell to insert the element---------------------O(1)

Step 4: SizeofTree++

Step 5: HeapifyBottomToTop(SizeofTree)-------------------------------O(log n) // this is to swap the elements if the heap does not satisfy min and max property

Time Complexity : O(log n)

Space Complexity : O(log n) // height of the tree

public void InsertElementInHeap(int value){

       if(sizeOfTree()<0){
             Console.WriteLine("Tree is empty");
      }
      else{
                //Insertion of value inside the array happens at the last index of the  array


                  arr[SizeofTree+1] = value;
                 sizeOfTree++;
        HeapifyBottomToTop(sizeOfTree);
        Console.WriteLine("Inserted " + value + " successfully in Heap !");
        levelOrder();
}//end of method

public void HeapifyBottomToTop(int index) {
        int parent = index / 2;
        // We are at root of the tree. Hence no more Heapifying is required.
        if (index <= 1) {
            return;
        }
        // If Current value is smaller than its parent, then we need to swap
        if (arr[index] < arr[parent]) {
            int tmp = arr[index];
            arr[index] = arr[parent];
            arr[parent] = tmp;
        }
        HeapifyBottomToTop(parent);
}//end of method

public void levelOrder() {
        Console.WriteLine("Printing all the elements of this Heap...");// Printing from 1 because 0th cell is dummy
        for (int i = 1; i <= sizeOfTree; i++) {
            System.out.print(arr[i] + " ");
        }
        Console.WriteLine("\n");
}//end of method

Extract a Value from Heap

 

The only value you can extract from the heap is root value. You cannot extract any child node from the heap. When you extract a root from the heap, navigate to the last element in the tree and make it root and adjust the tree.

 

Consider the below example.

 

In the above example "3" is the root node and we have extracted it. So when 3 is extracted, we need to replace 3 with the last element in the tree; i.e "100". Now 100 will become the root node. When "100" become the root node, the min and max property of the tree is not maintained. So we need to replace the elements in the tree by swapping elements from "Top to Bottom"

 

After Swapping,

Algorithm

 

Step1: ExtractRootElement() ----------------O(1)

Step2: If(SizeofTree is null) return 0--------O(1)

Step 3: else get the root------------------------O(1)

Step4: Decrement the Sizeof heap----------O(1)

Step5: Sort the heap elements -------------O(log n)

Time Complexity : O(log n)

Space Complexity : O(log n) // height of the tree

//Extract Head of Heap
    public int extractHeadOfHeap() {
        if(sizeOfTree == 0) {
            Console.WriteLine("Heap is empty !");
            return -1;
        }else {
            Console.WriteLine("Head of the Heap is: " + arr[1]);
            Console.WriteLine("Extracting it now...");
            int extractedValue = arr[1];
            arr[1] = arr[sizeOfTree]; //Replacing with last element of the array
            sizeOfTree--;
            HeapifyTopToBottom(1);
            System.out.println("Successfully extracted value from Heap.");
            levelOrder();
            return extractedValue;
        }
}//end of method

public void HeapifyTopToBottom(int index) {
        int left  = index*2;
        int right = (index*2)+1;
        int smallestChild = 0;

        if (sizeOfTree < left) { //If there is no child of this node, then nothing to do. Just return.
            return;
        }else if (sizeOfTree == left) { //If there is only left child of this node, then do a comparison and return.
            if(arr[index] > arr[left]) {
                int tmp = arr[index];
                arr[index] = arr[left];
                arr[left] = tmp;
            }
            return;
        }else { //If both children are there
            if(arr[left] < arr[right]) { //Find out the smallest child
                smallestChild = left;
            }else {
                smallestChild = right;
            }
            if(arr[index] > arr[smallestChild]) { //If Parent is greater than smallest child, then swap
                int tmp = arr[index];
                arr[index] = arr[smallestChild];
                arr[smallestChild] = tmp;
            }
        }
        HeapifyTopToBottom(smallestChild);
    }//end of method

Delete Entire Heap

 

Algorithm

 

Step1: DeleteHeap() -------------O(1)

Step2: set arr equals null--------O(1)

 

Time Complexity : O(1)

Space Complexity : O(1)

 

Last but not least. "Reference based Binary Heap"

 

Limitations of "Reference based Binary Heap" (Linked List Implementation). 

1. The Problem arises when we need to extract the element from the heap: Since it is reference based, the memory pointers needs to be maintained when swapping elements
2. Time and Space Complexity of Reference based heaps are always O(n). So we do not use it.