This tutorial explains what is Java Heap Data Structure & related concepts such as Min Heap, Max Heap, Heap Sort, Stack vs Heap with examples:
A heap is a special data structure in Java. A heap is a tree-based data structure and can be classified as a complete binary tree. All the nodes of the heap are arranged in a specific order.
- Heap Data Structure In Java
- Binary Heap
- Min Heap In Java
- Min Heap Algorithm
- Min Heap Implementation In Java
- Max Heap In Java
- Priority Queue Min Heap In Java
- Priority Queue Max Heap In Java
- Heap Sort In Java
- Heap Sort Algorithm In Java
- Heap Sort Implementation In Java
- Stack Vs Heap In Java
- Frequently Asked Questions
- Recommended Reading
Heap Data Structure In Java
In the heap data structure, the root node is compared with its children and arranged according to the order. So if a is a root node and b is its child, then the property, key (a)>= key (b) will generate a max heap.
The above relation between the root and the child node is called as “Heap Property”.
Depending on the order of parent-child nodes, the heap is generally of two types:
#1) Max-Heap: In a Max-Heap the root node key is the greatest of all the keys in the heap. It should be ensured that the same property is true for all the subtrees in the heap recursively.
The below diagram shows a Sample Max Heap. Note that the root node is greater than its children.
#2) Min-Heap: In the case of a Min-Heap, the root node key is the smallest or minimum among all the other keys present in the heap. As in Max heap, this property should be recursively true in all the other subtrees in the heap.
An example, of a Min-heap tree, is shown below. As we can see, the root key is the smallest of all the other keys in the heap.
A heap data structure can be used in the following areas:
- Heaps are mostly used to implement Priority Queues.
- Especially min-heap can be used to determine the shortest paths between the vertices in a Graph.
As already mentioned, the heap data structure is a complete binary tree that satisfies the heap property for root and the children. This heap is also called as a binary heap.
A binary heap fulfills the below properties:
- A binary heap is a complete binary tree. In a complete binary tree, all the levels except the last level are completely filled. At the last level, the keys are as far as left as possible.
- It satisfies the heap property. The binary heap can be max or min-heap depending on the heap property it satisfies.
A binary heap is normally represented as an Array. As it is a complete binary tree, it can easily be represented as an array. Thus in an array representation of binary heap, the root element will be A where A is the array used to represent the binary heap.
So in general for any ith node in the binary heap array representation, A[i], we can represent the indices of other nodes as shown below.
|A [(i-1)/2]||Represents the parent node|
|A[(2*i)+1]||Represents the left child node|
|A[(2*i)+2]||Represents the right child node|
Consider the following binary heap:
The array representation of the above min binary heap is as follows:
As shown above, the heap is traversed as per the level order i.e. the elements are traversed from left to right at each level. When the elements at one level are exhausted, we move on to the next level.
Next, we will implement the binary heap in Java.
The below program demonstrates the binary heap in Java.
nHeap = 7 4 6 1 3 2 5
Min Heap In Java
A min-heap in Java is a complete binary tree. In min-heap, the root node is smaller than all the other nodes in the heap. In general, the key value of each internal node is smaller than or equal to its child nodes.
As far as array representation of min-heap is concerned, if a node is stored at position ‘i’, then its left child node is stored at position 2i+1 and then the right child node is at position 2i+2. The position (i-1)/2 returns its parent node.
Enlisted below are the various operations supported by min-heap.
#1) Insert (): Initially, a new key is added at the end of the tree. If the key is larger than its parent node, then the heap property is maintained. Otherwise, we need to traverse the key upwards to fulfill the heap property. Insertion operation in min heap takes O (log n) time.
#2) extractMin (): This operation removes the minimum element from the heap. Note that the heap property should be maintained after removing the root element (min element) from the heap. This entire operation takes O (Logn).
#3) getMin (): getMin () returns the root of the heap which is also the minimum element. This operation is done in O (1) time.
Given below is an example tree for a Min-heap.
The above diagram shows a min-heap tree. We see that the root of the tree is the minimum element in the tree. As the root is at location 0, its left child is placed at 2*0 + 1 = 1 and right child is at 2*0 + 2 = 2.
Min Heap Algorithm
Given below is the algorithm for building a min-heap.
Min Heap Implementation In Java
We can implement the min-heap either using array or priority queues. Implementing min-heap using priority queues is the default implementation as a priority queue is implemented as min-heap.
The following Java program implements the min-heap using Arrays. Here we use array representation for heap and then apply heapify function to maintain the heap property of each element added to the heap. Finally, we display the heap.
Max Heap In Java
A max heap is also a complete binary tree. In a max heap, the root node is greater than or equal to the child nodes. In general, the value of any internal node in a max heap is greater than or equal to its child nodes.
While max heap is mapped to an array, if any node is stored at position ‘i’, then its left child is stored at 2i +1 and the right child is stored at 2i + 2.
Typical Max-heap will look as shown below:
In the above diagram, we see that the root node is the largest in heap and its child nodes have values smaller than the root node.
Similar to min-heap, the max heap can also be represented as an array.
So if A is an array that represents Max heap then A  is the root node. Similarly, if A[i] is any node in the max heap, then the following are the other adjacent nodes that can be represented using an array.
- A [(i-1)/2] represents the parent node of A[i].
- A [(2i +1)] represents the left child node of A[i].
- A [2i+2] returns the right child node of A[i].
The operations that can be performed on the Max Heap are given below.
#1) Insert: Insert operation inserts a new value in the max heap tree. It is inserted at the end of the tree. If the new key (value) is smaller than its parent node, then the heap property is maintained. Otherwise, the tree needs to be heapified to maintain the heap property.
The time complexity of insert operation is O (log n).
#2) ExtractMax: The operation ExtractMax removes the maximum element (root ) from the max heap. The operation also heapifies the max heap to maintain the heap property. The time complexity of this operation is O (log n).
#3) getMax: getMax operation returns the root node of the max heap with the time complexity of O (1).
The below Java program implements the max heap. We make use of ArrayList here to represent the max heap elements.
Priority Queue Min Heap In Java
The priority queue data structure in Java can be directly used to represent the min-heap. By default, the priority queue implements min-heap.
The below program demonstrates the min-heap in Java using the Priority Queue.
Priority Queue Max Heap In Java
To represent the max heap in Java using the Priority queue, we have to use Collections.reverseOrder to reverse the min-heap. The priority queue directly represents a min-heap in Java.
We have implemented the Max Heap using a Priority queue in the below program.
Heap Sort In Java
Heap sort is a comparison sort technique similar to selection sort wherein we select a maximum element in the array for each iteration. Heap sort makes use of Heap data structure and sorts the elements by creating min or max heap out of the array elements to be sorted.
We have already discussed that in min and max heap, the root node contains the minimum and maximum element respectively of the array. In heap sort, the root element of the heap (min or max) is removed and moved to the sorted array. The remaining heap is then heapified to maintain the heap property.
So we have to perform two steps recursively to sort the given array using heap sort.
- Build a heap from the given array.
- Repeatedly remove the root element from the heap and move it to the sorted array. Heapify the remaining heap.
Time Complexity of Heap sort is O (n log n) in all the cases. The space complexity is O (1).
Heap Sort Algorithm In Java
Given below are the heap sort algorithms to sort the given array in ascending and descending order.
#1) Heap Sort algorithm to sort in ascending order:
- Create a max heap for the given array to be sorted.
- Delete the root (maximum value in the input array) and move it to the sorted array. Place the last element in the array at the root.
- Heapify the new root of the heap.
- Repeat steps 1 and 2 till the entire array is sorted.
#2) Heap Sort algorithm to sort in descending order:
- Construct a min Heap for the given array.
- Remove the root (minimum value in the array) and swap it with the last element in the array.
- Heapify the new root of the heap.
- Repeat steps 1 and 2 till the entire array is sorted.
Heap Sort Implementation In Java
The below Java program uses heap sort to sort an array in ascending order. For this, we first construct a max heap and then recursively swap and heapify the root element as specified in the above algorithm.
The overall time complexity of the heap sort technique is O (nlogn). The time complexity of the heapify technique is O (logn). While the time complexity of building the heap is O (n).
Stack Vs Heap In Java
Let’s now tabularize some of the differences between a Stack data structure and heap.
|A stack is a linear data structure.||A heap is a hierarchical data structure.|
|Follows LIFO (Last In, First Out) ordering.||Traversal is in level order.|
|Mostly used for static memory allocation.||Used for dynamic memory allocation.|
|Memory is allocated contiguously.||Memory is allocated in random locations.|
|Stack size is limited according to the Operating system.||No limit on heap size enforced by the Operating system.|
|Stack has access to local variables only.||Heap has global variables allocated to it.|
|Access is faster.||Slower than the stack.|
|The allocation/deallocation of memory is automatic.||Allocation/deallocation needs to be done manually by the programmer.|
|The stack can be implemented using Arrays, Linked List, ArrayList, etc. or any other linear data structures.||Heap is implemented using Arrays or trees.|
|Cost of maintenance if less.||More costly to maintain.|
|May result in a shortage of memory as memory is limited.||No shortage of memory but may suffer from memory fragmentation.|
Frequently Asked Questions
Q #1) Is stack faster than Heap?
Answer: A stack is faster than heap as access is linear in stack compared to the heap.
Q #2) What is a Heap used for?
Answer: Heap is mostly used in algorithms that find the minimum or shortest path between two points like Dijkstra’s algorithm, to sort using heap sort, for priority queue implementations (min-heap), etc.
Q #3) What is a Heap? What are its types?
Answer: A heap is a hierarchical, tree-based data structure. A heap is a complete binary tree. Heaps are of two types i.e. Max heap in which the root node is the largest among all the nodes; Min heap in which the root node is the smallest or minimum among all the keys.
Q #4) What are the advantages of Heap over a stack?
Answer: The major advantage of the heap over stack is in heap, the memory is dynamically allocated and hence there is no limit on how much memory can be used. Secondly, only local variables can be allocated on the stack while we can also allocate global variables on the heap.
Q #5) Can Heap have duplicates?
Answer: Yes, there are no restrictions on having nodes with duplicate keys in the heap as the heap is a complete binary tree and it does not satisfy the properties of the binary search tree.
In this instructional exercise, we have talked about the kinds of store and load sort utilizing kinds of stack. We have likewise seen the definite execution of its sorts in Java.