Core Java

Max Heap Java Example

In this article we will show what is max heap in Java and why we use it.

1. Introduction

A max heap binary tree is a complete binary tree in which the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root. A typical representation of a Max-heap binary tree is as follows:

Max Heap Java - max-heap binary tree representation
A typical max-heap binary tree representation

1.1 Array representation of the binary Tree

This is a complete binary tree and is typically represented as an array. The root element is denoted by Arr[0]. The following list shows the array representation of the associated nodes of a given node i i.e. Arr[i] in a max-heap binary tree:

  • Arr[(i-1)/2] represents the parent node.
  • Arr[(2*i)+1] represents the left child node.
  • Arr[(2*i)+2] represents the right child node.

1.2 Operations in heap binary tree

The operations that are performed on a heap binary tree are listed below:

  • Peek(): It returns the root element. This is the maximum element of heap. Time Complexity of this operation is O(1).
  • Poll(): Removes the maximum element from MaxHeap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()) after removing the root.
  • add(): Inserting a new key takes O(Logn) time. We add a new key at the end of the tree. If a new key is smaller than its parent, then we don’t need to do anything. Otherwise, we need to traverse up to fix the violated heap property.

2. The Java implementation

We will now see a demo example for the Max-heap binary tree using Java and understand how the different operations work on it.

// Java program to implement Max Heap 
public class MaxHeap { 
    private int[] Heap; 
    private int size; 
    private int maxsize; 
  
    // Constructor to initialize an 
    // empty max heap with given maximum 
    // capacity. 
    public MaxHeap(int maxsize) 
    { 
        this.maxsize = maxsize; 
        this.size = 0; 
        Heap = new int[this.maxsize + 1]; 
        Heap[0] = Integer.MAX_VALUE; 
    } 
  
    // Returns position of parent 
    private int parent(int pos) 
    { 
        return pos / 2; 
    } 
  
    // Below two functions return left and 
    // right children. 
    private int leftChild(int pos) 
    { 
        return (2 * pos); 
    } 
    private int rightChild(int pos) 
    { 
        return (2 * pos) + 1; 
    } 
  
    // Returns true of given node is leaf 
    private boolean isLeaf(int pos) 
    { 
        if (pos >= (size / 2) && pos <= size) { 
            return true; 
        } 
        return false; 
    } 
  
    private void swap(int fpos, int spos) 
    { 
        int tmp; 
        tmp = Heap[fpos]; 
        Heap[fpos] = Heap[spos]; 
        Heap[spos] = tmp; 
    } 
  
    // A recursive function to max heapify the given 
    // subtree. This function assumes that the left and 
    // right subtrees are already heapified, we only need 
    // to fix the root. 
    private void maxHeapify(int pos) 
    { 
        if (isLeaf(pos)) 
            return; 
  
        if (Heap[pos] < Heap[leftChild(pos)] ||  
            Heap[pos] < Heap[rightChild(pos)]) { 
  
            if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) { 
                swap(pos, leftChild(pos)); 
                maxHeapify(leftChild(pos)); 
            } 
            else { 
                swap(pos, rightChild(pos)); 
                maxHeapify(rightChild(pos)); 
            } 
        } 
    } 
  
    // Inserts a new element to max heap 
    public void add(int element) 
    { 
        Heap[++size] = element; 
  
        // Traverse up and fix violated property 
        int current = size; 
        while (Heap[current] > Heap[parent(current)]) { 
            swap(current, parent(current)); 
            current = parent(current); 
        } 
    } 
  
    public void display() 
    { 
        for (int i = 1; i <= size / 2; i++) { 
            System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + 
                      Heap[2 * i] + " RIGHT CHILD :" + Heap[2 * i + 1]); 
            System.out.println(); 
        } 
    } 
  
    // Remove an element from max heap 
    public int poll() 
    { 
        int popped = Heap[1]; 
        Heap[1] = Heap[size--]; 
        maxHeapify(1); 
        return popped; 
    } 
  
    public static void main(String[] arg) 
    { 
        System.out.println("The Max Heap is "); 
        MaxHeap maxHeap = new MaxHeap(20); 
        maxHeap.add(15); 
        maxHeap.add(13); 
        maxHeap.add(7); 
        maxHeap.add(5); 
        maxHeap.add(52); 
        maxHeap.add(23); 
        maxHeap.add(16); 
        maxHeap.add(9); 
        maxHeap.add(21); 
  
        maxHeap.display(); 
        System.out.println("The max val is " + maxHeap.poll()); 
    } 
}

Output

The Max Heap is 
 PARENT : 52 LEFT CHILD : 21 RIGHT CHILD :23
 PARENT : 21 LEFT CHILD : 15 RIGHT CHILD :13
 PARENT : 23 LEFT CHILD : 7 RIGHT CHILD :16
 PARENT : 15 LEFT CHILD : 5 RIGHT CHILD :9
The max val is 52

3. Max Heap used as a Priority Queue

Priority Queue is an abstract data structure similar to a regular queue or a stack data structure in which each element has an additional field known as Priority associated with it and is served based on its priority. In Java, this can be used as a Priority Queue which we will see in the following demo.

// Java program to demonstrate working of PriorityQueue as a Max Heap 
import java.util.*; 
  
class PriorityQueueDemo { 
  public static void main(String args[]) 
    { 
        // Creating empty priority queue 
        PriorityQueue<Integer> pQueue =  new PriorityQueue<Integer>(Collections.reverseOrder()); 
  
        // Adding items to the pQueue using add() 
        pQueue.add(50); 
        pQueue.add(30); 
        pQueue.add(20); 
        pQueue.add(10); 
  
        // Displaying the highest priority element 
        System.out.println("Head value using peek function:" +  pQueue.peek()); 
  
        // Printing all elements 
        System.out.println("The queue elements:"); 
        Iterator itr = pQueue.iterator(); 
        while (itr.hasNext()) 
            System.out.println(itr.next()); 
  
        // Removing the top priority element (or head) and 
        // printing the modified pQueue using poll() 
        pQueue.poll(); 
        System.out.println("After removing an element with poll function:"); 
        Iterator<Integer> itr2 = pQueue.iterator(); 
        while (itr2.hasNext()) 
            System.out.println(itr2.next()); 
  
        // Removing element 20 using remove() 
        pQueue.remove(20); 
        System.out.println("after removing 20 with remove function:"); 
        Iterator<Integer> itr3 = pQueue.iterator(); 
        while(itr3.hasNext()) 
            System.out.println(itr3.next()); 
  
        // Check if an element is present using contains() 
        boolean b = pQueue.contains(20); 
        System.out.println("Priority queue contains 20 or not?: " + b); 
  
        // Getting objects from the queue using toArray() in an array and display the array 
        Object[] arr = pQueue.toArray(); 
        System.out.println("Value in array: "); 
        for(int i = 0; i < arr.length; i++) 
            System.out.println("Value: " + arr[i].toString()); 
    } 
} 

Output

Head value using peek function:50
The queue elements:
50
30
20
10
After removing an element with poll function:
30
10
20
after removing 20 with remove function:
30
10
Priority queue contains 20 or not?: false
Value in array: 
Value: 30
Value: 10

4. Applications of Max Heap Binary Tree

Max Heap Binary tree can be used in various areas of Data structure, some of which is highlighted below:

  • Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nLogn) time.
  • Priority Queue: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and pop(), decreaseKey() operations in O(logn) time. Binomial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform unions also efficiently.
  • Many data structure problems can be efficiently solved using Max-Heaps. See the following for example. a. K’th Largest Element in an array.

5. Conclusion

In this tutorial, we understood the definition and implementation of the Binary tree in Java and also we understood how it can be used to solve many data structure problems such as Priority Queue and Finding Kth largest element in an array.

6. References

7. Download the source code

The following code shows the usage of the Max Heap Binary tree and its implementation as a Priority Queue.

Download
You can download the full source code of this example here: Max Heap Java Example

Gaurav Verma

I am Gaurav Verma from Kolkata, India. I have done Bachelors of Technology in Computer Science & Engineering from Narula Institute of Technology under West Bengal University of Technology. I joined NIIT LTD. as a Technical Trainer in 2007 and trained students pursuing GNIIT and Bsc.IT curriculum as well as modular courses in various technologies like Java, .Net and Open Source technologies. I have been a very enthusiastic Java programmer and take lot of interest in programming through Java language and also develop Standalone and web applications using Java technologies. My favourite pass time are Solving Puzzles, Sudoku, watching documentaries etc.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments
Back to top button