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:
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
- https://www.geeksforgeeks.org/binary-heap/
- http://www.btechsmartclass.com/data_structures/max-heap.html
- https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
- https://www.educative.io/edpresso/min-heap-vs-max-heap
7. Download the source code
The following code shows the usage of the Max Heap Binary tree and its implementation as a Priority Queue.
You can download the full source code of this example here: Max Heap Java Example
