Heap implementation in Java

In Java, Heap is a special type of data structure where the root node or parent node is compared with its left and right children and arranged according to the order. Suppose, x is a root node and y is the child node, property key(x)<= key(y) will generate min-heap, and that relation is referred to as “Heap Property”.

Based on the order of the parent and child nodes, Heap can be classified in two forms, i.e., Min heap and Max heap. Let’s understand both of them one by one and implement the code in Java.

Min heap

Min heap is a special type of heap data structure that is a complete binary tree in itself . Min heap has the following properties:

Root node value is always smaller in comparison to the other nodes of the heap.
Each internal node has a key value that is always smaller or equal to its children.

We can perform the following three operations in Min heap:

insertNode()

We can perform insertion in the Min heap by adding a new key at the end of the tree. If the value of the inserted key is smaller than its parent node, we have to traverse the key upwards for fulfilling the heap property. The insertion process takes O(log n) time.

extractMin()

It is one of the most important operations which we perform to remove the minimum value node, i.e., the root node of the heap. After removing the root node, we have to make sure that heap property should be maintained. The extractMin() operation takes O(Logn) time to remove the minimum element from the heap.

getMin()

The getMin() operation is used to get the root node of the heap, i.e., minimum element in O(1) time.

Example:

Heap implementation in Java

Min heap Algorithm

  proceduredesign_min_heap  Array arr: of size n => array of elements  // call min_heapify procedure for each element of the array to form min heap  repeat for (k = n/2 ; k >= 1 ; k–)  call procedure min_heapify (arr, k);  proceduremin_heapify (vararr[ ] , var k, varn)  {  varleft_child  = 2*k;  varright_child = 2*k+1;  var smallest;  if(left_child<= n and arr[left_child ] [>

MinHeapJavaImplementation.java

  // import required classes and packages  packagetutorAspire.javacodes;    importjava.util.Scanner;    // create class MinHeap to construct Min heap in Java  classMinHeap {   // declare array and variables  privateint[] heapData;   privateintsizeOfHeap;   privateintheapMaxSize;     private static final int FRONT = 1;       //use constructor to initialize heapData array  publicMinHeap(intheapMaxSize)  {   this.heapMaxSize = heapMaxSize;   this.sizeOfHeap = 0;   heapData = new int[this.heapMaxSize + 1];   heapData[0] = Integer.MIN_VALUE;       }         // create getParentPos() method that returns parent position for the node   privateintgetParentPosition(int position)  {   return position / 2;       }         // create getLeftChildPosition() method that returns the position of left child   privateintgetLeftChildPosition(int position)  {   return (2 * position);       }         // create getRightChildPosition() method that returns the position of right child  privateintgetRightChildPosition(int position)  {   return (2 * position) + 1;       }         // checks whether the given node is leaf or not  privatebooleancheckLeaf(int position)  {   if (position >= (sizeOfHeap / 2) && position <= sizeOfHeap) {   return true;           }   return false;       }         // create swapNodes() method that perform swapping of the given nodes of the heap       // firstNode and secondNode are the positions of the nodes  private void swap(intfirstNode, intsecondNode)  {   int temp;   temp = heapData[firstNode];   heapData[firstNode] = heapData[secondNode];   heapData[secondNode] = temp;       }         // create minHeapify() method to heapify the node for maintaining the heap property  private void minHeapify(int position)  {             //check whether the given node is non-leaf and greater than its right and left child  if (!checkLeaf(position)) {   if (heapData[position] >heapData[getLeftChildPosition(position)] || heapData[position] >heapData[getRightChildPosition(position)]) {                     // swap with left child and then heapify the left child   if (heapData[getLeftChildPosition(position)] = heapMaxSize) {   return;           }   heapData[++sizeOfHeap] = data;   int current = sizeOfHeap;     while (heapData[current] = 1; position–) {   minHeapify(position);           }       }         // create removeRoot() method for removing minimum element from the heap  publicintremoveRoot()  {   intpopElement = heapData[FRONT];   heapData[FRONT] = heapData[sizeOfHeap–];   minHeapify(FRONT);   returnpopElement;       }   }    // create MinHeapJavaImplementation class to create heap in Java  classMinHeapJavaImplementation{    // main() method start  public static void main(String[] arg)  {   // declare variable  intheapSize;    // create scanner class object  Scanner sc = new Scanner(System.in);    System.out.println(“Enter the size of Min Heap”);  heapSize = sc.nextInt();    MinHeapheapObj = new MinHeap(heapSize);    for(inti = 1; i<= heapSize; i++) {  System.out.print(“Enter “+i+” element: “);  int data = sc.nextInt();  heapObj.insertNode(data);  }            // close scanner class obj  sc.close();            //construct a min heap from given data  heapObj.designMinHeap();             //display the min heap data  System.out.println(“The Min Heap is “);   heapObj.displayHeap();             //removing the root node from the heap  System.out.println(“After removing the minimum element(Root Node) “+heapObj.removeRoot()+”, Min heap is:”);   heapObj.displayHeap();         }   }  [getparentposition(current)])>[getrightchildposition(position)])>

Output:

Heap implementation in Java

Max heap

Max heap is another special type of heap data structure that is also a complete binary tree in itself in Java. Max heap has the following properties:

Root node value is always greater in comparison to the other nodes of the heap.
Each internal node has a key value that is always greater or equal to its children.

We can perform the following three operations in Max heap:

insertNode()

We can perform insertion in the Max heap by adding a new key at the end of the tree. If the value of the inserted key is greater than its parent node, we have to traverse the key upwards for fulfilling the heap property. The insertion process takes O(log n) time.

extractMax()

It is one of the most important operations which we perform to remove the maximum value node, i.e., the root node of the heap. After removing the root node, we have to make sure that heap property should be maintained. The extractMax() operation takes O(Log n) time to remove the maximum element from the heap.

getMax()

The getMax() operation is used to get the root node of the heap, i.e., maximum element in O(1) time.

Example:

Heap implementation in Java

Min heap Algorithm

  proceduredesign_max_heap  Array arr: of size n => array of elements  // call min_heapify procedure for each element of the array to form max heap  repeat for (k = n/2 ; k >= 1 ; k–)  call procedure max_heapify (arr, k);  proceduremin_heapify (vararr[ ] , var k, varn)  {  varleft_child  = 2*k + 1;  varright_child = 2*k+ 2;  if(left_child<= n and arr[left_child] >arr[ largest ] )  largest = left_child;  else  largest = k;  if(right_child<= n and arr[right_child] >arr[largest] )  largest = right_child;  if(largest != k)      {  swaparr[ k ] and  arr[ largest ]);  callmax_heapify (arr, largest, n);      }   }  

MaxHeapJavaImplementation.java

  //import required classes and packages  packagetutorAspire.javacodes;    importjava.util.Scanner;    //create class MinHeap to construct Min heap in Java  classMaxHeap {   // declare array and variables  privateint[] heapData;   privateintsizeOfHeap;   privateintheapMaxSize;     private static final int FRONT = 1;     //use constructor to initialize heapData array  publicMaxHeap(intheapMaxSize)  {   this.heapMaxSize = heapMaxSize;   this.sizeOfHeap = 0;   heapData = new int[this.heapMaxSize];  }     // create getParentPos() method that returns parent position for the node   privateintgetParentPosition(int position)  {   return (position – 1) / 2;   }     // create getLeftChildPosition() method that returns the position of left child   privateintgetLeftChildPosition(int position)  {   return (2 * position);   }     // create getRightChildPosition() method that returns the position of right child  privateintgetRightChildPosition(int position)  {   return (2 * position) + 1;   }     // checks whether the given node is leaf or not  privatebooleancheckLeaf(int position)  {   if (position > (sizeOfHeap / 2) && position <= sizeOfHeap) {   return true;   }   return false;   }     // create swapNodes() method that perform swapping of the given nodes of the heap   // firstNode and secondNode are the positions of the nodes  private void swap(intfirstNode, intsecondNode)  {   int temp;   temp = heapData[firstNode];   heapData[firstNode] = heapData[secondNode];   heapData[secondNode] = temp;   }     // create maxHeapify() method to heapify the node for maintaining the heap property  private void maxHeapify(int position)  {          //check whether the given node is non-leaf and greater than its right and left child  if (!checkLeaf(position)) {   if (heapData[position] heapData[getRightChildPosition(position)]) {   swap(position, getLeftChildPosition(position));   maxHeapify(getLeftChildPosition(position));                }                  // Swap with the right child and heapify the right child   else {   swap(position, getRightChildPosition(position));   maxHeapify(getRightChildPosition(position));                }            }        }   }     // create insertNode() method to insert element in the heap  public void insertNode(int data)  {   heapData[sizeOfHeap] = data;   int current = sizeOfHeap;     while (heapData[current] >heapData[getParentPosition(current)]) {    swap(current, getParentPosition(current));   current = getParentPosition(current);   }   sizeOfHeap++;  }     // create displayHeap() method to print the data of the heap   public void displayHeap()  {   System.out.println(“PARENT NODE” + “t” + “LEFT CHILD NODE” + “t” + “RIGHT CHILD NODE”);  for (int k = 0; k [getleftchildposition(position)]>

Output:

Heap implementation in Java

Next TopicHow to Check null in Java

Heap implementation in Java

Heap implementation in Java

Min heap

insertNode()

extractMin()

getMin()

Max heap

insertNode()

extractMax()

getMax()

LCD Interfacing with AVR

JavaScript TypedArray entries() Method

You may also like