Max Heap in Java

Last Updated on December 14, 2022 by Prepbytes

What is Heap?

Heap is a special kind of complete binary tree in which the all node has a value greater (or smaller ) than all of its children .

A complete binary tree is a binary tree where all levels are completely filled except the last level which can be complete or incomplete . All nodes should be filled from left to right .

There are two types of heap , Min heap and Max heap . In Max heap all nodes have value greater than the children’s value whereas in Min heap all nodes have value smaller than the children’s value .

In this Article we will focus on Max heap only .

What is Max-heap?

A Heap in which all nodes have a value greater than all its children , is Max heap .
i.e for a node its value is more than the value of its left child and the value of its right child and this property is recursively true for every node .In other words , we can also say that any node
at a certain level has more value than all nodes below its level.

Representation of Max-heap

• A Max heap is represented using an Array .
• A node at i-th position has its left child at 2 i+1 and right child at 2 i+2 .
• A node at i-th position has its parent at (i-1)/2 .
• In max heap , heap[i] > heap[2 i+1] and heap[i] > heap[2 i+2]

• Node at position 0 has left child at 2 0+1 = 1 and right child at 2 0+2 = 2 positions .

• Value of node at 0 is greater than the value of nodes at 1 and 2.

• Node at position 1 has left child at 2 1+1 = 3 and right child at 2 1+2 = 4 positions .

• Node at position 2 has only left child at position 2 * 2+1=5 .

• Nodes at position 3,4 and 5 are leaf nodes with no child .

Operations on Max heap

getMax() : This method will return the maximum number in the heap .

deleteMax() : The method will delete the node with maximum value .Following steps are taken in this method :

1. Swap root node with the rightmost node .
2. Delete rightmost node
3. Call heapify method for root
   Because of heapify() , the time complexity of this method is O(logn) .

heapify() : This will be the private method for the MaxHeap class . The method ensures that heap property is maintained .

insert() : The method is used to insert new nodes in the max heap . A new node is inserted at the end of the heap array , and we keep on swapping this node with the parent node if it is violating heap property .

size() : returns size of heap.

Time complexity of all operations is O(logn) except getMax() and size().

Implementation of Max heap in Java

Implementation of Max heap using java libraries

We can also implement max heap using PriorityQueue class . By default it creates a min heap , to create a max heap we can use Collections.reverseOrder() .

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes 
		PriorityQueue<Integer> heap = new PriorityQueue<Integer>(Collections.reverseOrder());
        heap.add(11);
        heap.add(2);
        heap.add(10);
        heap.add(7);
        heap.add(3);
        heap.add(8);
        System.out.println("size of heap : " + heap.size());
        System.out.println("max in heap : " +heap.peek());
        heap.poll();
        System.out.println("after deletion");
        System.out.println("size of heap : " + heap.size());
        System.out.println("max in heap : " +heap.peek());
	}
}

This article tried to discuss Max heap in Java. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.