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.
Binary Heap In C# 

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 
  1. Public Class BinaryHeapExample{  
  2.   
  3.     int[] arr;  
  4.    int  sizeOfTree;  
  5.      // Create a constructor  
  6.    public BinaryHeapExample(int size){  
  7.      //We are adding size+1, because array index 0 will be blank.  
  8.       int arr = new int[size+1];  
  9.      this.sizeofTree=0;  
  10.      Console.WriteLine("Empty heap has been created Successfully");  
  11.     }   
  12.  }       
  13.      
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)
  1. public int PeekOfHeap()  
  2. {  
  3.    if(SizeOfTree == 0)  
  4.       return 0;  
  5.    else  
  6.       return arr[1];  
  7. }  
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)
  1. public int SizeOfHeap(){  
  2.   
  3.    Console.WriteLine("The size of the heap is:"+ SizeOfTree);  
  4.   return SizeOfTree;  
  5. }  

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. 
Binary Heap In C# 
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"
Binary Heap In C#
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
  1. public void InsertElementInHeap(int value){  
  2.     
  3.        if(sizeOfTree()<0){  
  4.              Console.WriteLine("Tree is empty");  
  5.       }  
  6.       else{  
  7.                 //Insertion of value inside the array happens at the last index of the  array
  8.                   
  9.        
  10.                   arr[SizeofTree+1] = value;  
  11.                  sizeOfTree++;  
  12.         HeapifyBottomToTop(sizeOfTree);  
  13.         Console.WriteLine("Inserted " + value + " successfully in Heap !");  
  14.         levelOrder();  
  15. }//end of method  
  16.   
  17. public void HeapifyBottomToTop(int index) {  
  18.         int parent = index / 2;  
  19.         // We are at root of the tree. Hence no more Heapifying is required.  
  20.         if (index <= 1) {  
  21.             return;  
  22.         }  
  23.         // If Current value is smaller than its parent, then we need to swap  
  24.         if (arr[index] < arr[parent]) {  
  25.             int tmp = arr[index];  
  26.             arr[index] = arr[parent];  
  27.             arr[parent] = tmp;  
  28.         }  
  29.         HeapifyBottomToTop(parent);  
  30. }//end of method  
  31.   
  32. public void levelOrder() {  
  33.         Console.WriteLine("Printing all the elements of this Heap...");// Printing from 1 because 0th cell is dummy  
  34.         for (int i = 1; i <= sizeOfTree; i++) {  
  35.             System.out.print(arr[i] + " ");  
  36.         }  
  37.         Console.WriteLine("\n");  
  38. }//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.
 Binary Heap In C#
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"
Binary Heap In C# 
After Swapping,
Binary Heap In C#
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
  1. //Extract Head of Heap  
  2.     public int extractHeadOfHeap() {  
  3.         if(sizeOfTree == 0) {  
  4.             Console.WriteLine("Heap is empty !");  
  5.             return -1;  
  6.         }else {  
  7.             Console.WriteLine("Head of the Heap is: " + arr[1]);  
  8.             Console.WriteLine("Extracting it now...");  
  9.             int extractedValue = arr[1];  
  10.             arr[1] = arr[sizeOfTree]; //Replacing with last element of the array  
  11.             sizeOfTree--;  
  12.             HeapifyTopToBottom(1);  
  13.             System.out.println("Successfully extracted value from Heap.");  
  14.             levelOrder();  
  15.             return extractedValue;  
  16.         }  
  17. }//end of method  
  18.   
  19. public void HeapifyTopToBottom(int index) {  
  20.         int left  = index*2;  
  21.         int right = (index*2)+1;  
  22.         int smallestChild = 0;  
  23.           
  24.         if (sizeOfTree < left) { //If there is no child of this node, then nothing to do. Just return.  
  25.             return;   
  26.         }else if (sizeOfTree == left) { //If there is only left child of this node, then do a comparison and return.  
  27.             if(arr[index] > arr[left]) {  
  28.                 int tmp = arr[index];  
  29.                 arr[index] = arr[left];  
  30.                 arr[left] = tmp;  
  31.             }  
  32.             return;  
  33.         }else { //If both children are there  
  34.             if(arr[left] < arr[right]) { //Find out the smallest child  
  35.                 smallestChild = left;  
  36.             }else {  
  37.                 smallestChild = right;  
  38.             }  
  39.             if(arr[index] > arr[smallestChild]) { //If Parent is greater than smallest child, then swap  
  40.                 int tmp = arr[index];  
  41.                 arr[index] = arr[smallestChild];  
  42.                 arr[smallestChild] = tmp;  
  43.             }  
  44.         }  
  45.         HeapifyTopToBottom(smallestChild);  
  46.     }//end of method  
  47.       

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.