Types of Heaps
There are two main types of heaps: max heaps & min heaps.
1. Max Heap: In a max heap, the key at the root node must be the largest among all the keys present in the heap. The same property must be recursively true for all sub-trees in the binary tree.
2. Min Heap: In a min heap, the key at the root node must be the smallest among all the keys present in the heap. The same property must be recursively true for all sub-trees in the binary tree.
The min-heap property is useful for algorithms like Dijkstra's Shortest Path, while the max-heap property is useful for algorithms like Heap Sort.
It's important to note that there is no ordering between siblings in a heap - the only requirement is that the parent node must be greater than (in a max heap) or less than (in a min-heap) both of its children.
Heaps are usually implemented with the help of arrays, with the array indices used to implicitly represent the tree structure based on the parent-child relationships. For a node at index i, its children are at indices 2i+1 & 2i+2, while its parent (if any) is at index floor((i-1)/2).
Heap Operations
The two main operations that can be performed on a heap are insertion & deletion.
1. Insertion
To insert a new element into a heap, we first append it to the end of the array (i.e., the bottom rightmost spot in the tree). Then, we compare this new element with its parent. If the new element is larger than its parent (in a max heap) or smaller than its parent (in a min-heap), we swap the two elements. We continue this process of comparing & swapping with the parent until the heap property is satisfied.
The step-by-step process for insertion is :
- Add the new element to the bottom rightmost spot in the tree (the end of the array).
- Compare the new element with its parent.
- If the parent is smaller than the new element (in a max heap) or larger than the new element (in a min-heap), swap them.
- Repeat steps 2 & 3 until the heap property is satisfied.
2. Deletion
Deletion in a heap always happens at the root. To delete the root element, we first replace it with the last element in the array (the bottom rightmost element in the tree). Then, we compare this new root with its children. If a child is larger than the new root (in a max heap) or smaller than the new root (in a min-heap), we swap the root with the larger (or smaller) child. We continue this process of comparing & swapping with the children until the heap property is satisfied.
Let’s see the step-by-step process for deletion:
- Replace the root element with the last element in the array.
- Compare the new root with its children.
- If a child is larger than the root (in a max heap) or smaller than the root (in a min-heap), swap the root with the larger (or smaller) child.
- Repeat steps 2 & 3 until the heap property is satisfied.
Note: These are the two fundamental operations on a heap. Other operations like finding the maximum or minimum element are trivial since the root always contains the maximum (in a max heap) or minimum (in a min-heap) element.
Heap Data Structure Applications
The wide range of applications are :
1. Heap Sort: Heap sort is a comparison-based sorting technique based on the binary heap data structure. It's similar to selection sort where we first find the minimum element & place it at the beginning. We repeat the same process for the remaining elements.
2. Priority Queue: A priority queue is an abstract data type that is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. Heaps are commonly used to implement priority queues.
3. Graph Algorithms: Heaps are used in graph algorithms like Dijkstra's Shortest Path and Prim's Minimum Spanning Tree.
4. Selection Algorithms: Heaps can be used to efficiently find the kth smallest (or largest) element in an array or other data structure. This is known as the selection problem.
5. System Resource Management: Many system kernels use heaps for scheduling processes, memory management, or maintaining other system resources.
6. Order Statistics: The Heap data structure can be used to find the kth smallest or kth largest element in a collection of n elements.
7. Big Data: In the realm of big data, heaps are often used in MapReduce implementations for sorting & finding the top k elements.
Basics of Heap Data Structure
Now that we understand what heaps are & some of their applications, let's understand the basics of how heaps work.
As mentioned earlier, a heap is a complete binary tree. This means that all levels of the tree are fully filled, except possibly the last level, which is filled from left to right. This property allows heaps to be efficiently stored in an array.
In an array representation of a heap, the first element (index 0) is the root of the heap. For any element at index i:
- Its left child is at index 2i + 1
- Its right child is at index 2i + 2
- Its parent is at index floor((i - 1) / 2)
The heap property (either max-heap or min-heap) is what distinguishes a heap from a regular binary tree. In a max-heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min-heap, the key of P is less than or equal to the key of C.
This property is crucial for efficient insertion & deletion operations, as it allows us to maintain the heap structure while only comparing a node with its parent or children.
Another important property of heaps is that they are not sorted structures. The only guarantee is that the root element is either the maximum (in a max heap) or the minimum (in a min-heap). The other elements are not in any particular order.
Other Types of Heap Data Structure
Even though max heaps & min heaps are the most common types of heaps, there are a few other specialized types of heaps that are used in specific scenarios, which are:
1. Binomial Heap: A binomial heap is a collection of binomial trees. It's similar to a binary heap but provides faster merge operations. In a binomial heap, each binomial tree follows the min-heap or max-heap property. Binomial heaps are often used in Dijkstra's algorithm to find the shortest path in a graph.
2. Fibonacci Heap: A Fibonacci heap is a collection of trees with a few additional constraints. Like binomial heaps, Fibonacci heaps are used to improve the asymptotic running time of Dijkstra's algorithm. Operations like insertion & finding the minimum are done in constant amortized time, while deletion & extracting the minimum take O(log n) amortized time.
3. Pairing Heap: A pairing heap is a type of heap data structure with a very simple implementation and excellent practical amortized performance. In a pairing heap, all operations are done by merging heaps. The heap is structured as a general tree, with no restrictions on the number of children each node can have.
4. Leftist Heap: A leftist heap is a variant of a binary heap. In a leftist heap, in addition to the heap property, there is an additional leftist property: the rank (or the distance to the nearest leaf) of any left child is always greater than or equal to the rank of its right sibling.
5. Skew Heap: A skew heap is a self-adjusting version of a leftist heap. In a skew heap, the leftist property is removed. Instead, whenever we join two skew heaps, we swap the left & right children of the root of the resulting heap. This self-adjusting operation tends to keep the heights of the two subtrees approximately equal.
Algorithms
Now let's look at the algorithm for the two main operations on a heap: insertion & deletion.
Insertion Algorithm
1. Add the new element to the end of the array (bottom rightmost spot in the tree).
2. Compare the new element with its parent.
3. If the parent is smaller than the new element (in a max heap) or larger than the new element (in a min heap), swap them.
4. Repeat steps 2 & 3 until the heap property is satisfied.
Here's the pseudocode for the insertion algorithm:
function insert(heap, element):
heap.append(element)
index = size(heap) - 1
while index > 0 and heap[parent(index)] < heap[index]:
swap(heap, index, parent(index))
index = parent(index)
Deletion Algorithm
1. Replace the root element with the last element in the array.
2. Compare the new root with its children.
3. If a child is larger than the root (in a max heap) or smaller than the root (in a min heap), swap the root with the larger (or smaller) child.
4. Repeat steps 2 & 3 until the heap property is satisfied.
Here's the pseudocode for the deletion algorithm:
function delete(heap):
if size(heap) == 0:
return "Heap is empty"
max = heap[0]
heap[0] = heap[size(heap) - 1]
heap.pop()
heapify(heap, 0)
return max
function heapify(heap, index):
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < size(heap) and heap[left] > heap[largest]:
largest = left
if right < size(heap) and heap[right] > heap[largest]:
largest = right
if largest != index:
swap(heap, index, largest)
heapify(heap, largest)
These are the basic algorithms for insertion & deletion in a heap. The `heapify` function is used to maintain the heap property after deletion.
Insert Element into Heap
Now let's see how to insert an element into a heap. We'll use a max heap for this example.
Suppose we have a max heap with the following elements: [50, 30, 20, 15, 10, 8, 16]
We want to insert the element 40 into this heap.
Step 1: Add 40 to the end of the array. The heap now looks like this:
[50, 30, 20, 15, 10, 8, 16, 40]
Step 2: Compare 40 with its parent (15).
40 is greater than 15, so we swap them. The heap now looks like this:
[50, 30, 20, 40, 10, 8, 16, 15]
Step 3: Compare 40 with its new parent (30).
40 is greater than 30, so we swap them. The heap now looks like this:
[50, 40, 20, 30, 10, 8, 16, 15]
Step 4: Compare 40 with its new parent (50).
40 is not greater than 50, so we stop.
The final heap after inserting 40 is:
[50, 40, 20, 30, 10, 8, 16, 15]
Let’s look at the python code to insert an element into a max heap:
def heapify_up(heap, index):
parent = (index - 1) // 2
if index > 0 and heap[parent] < heap[index]:
heap[parent], heap[index] = heap[index], heap[parent]
heapify_up(heap, parent)
def insert(heap, element):
heap.append(element)
heapify_up(heap, len(heap) - 1)
The `insert` function appends the new element to the end of the heap & then calls `heapify_up` to restore the heap property.
Delete Element from Heap
Now let's see how to delete an element from a heap. In a heap, we always delete the root element. We'll use a max heap for this example.
Suppose we have a max heap with the following elements: [50, 40, 20, 30, 10, 8, 16, 15]
Step 1: Replace the root (50) with the last element (15). The heap now looks like this:
[15, 40, 20, 30, 10, 8, 16]
Step 2: Compare 15 with its children (40 & 20).
15 is less than 40, so we swap 15 with the larger child (40). The heap now looks like this:
[40, 15, 20, 30, 10, 8, 16]
Step 3: Compare 15 with its new children (30 & 10).
15 is less than 30, so we swap 15 with the larger child (30). The heap now looks like this:
[40, 30, 20, 15, 10, 8, 16]
Step 4: Compare 15 with its new children (10 & 8).
15 is greater than both 10 & 8, so we stop.
The final heap after deleting the root is:
[40, 30, 20, 15, 10, 8, 16]
Let’s discuss the python code to delete the root from a max heap:
def heapify_down(heap, index):
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < len(heap) and heap[left] > heap[largest]:
largest = left
if right < len(heap) and heap[right] > heap[largest]:
largest = right
if largest != index:
heap[index], heap[largest] = heap[largest], heap[index]
heapify_down(heap, largest)
def delete(heap):
if not heap:
return None
root = heap[0]
heap[0] = heap[-1]
heap.pop()
heapify_down(heap, 0)
return root
The `delete` function replaces the root with the last element, pops the last element, & then calls `heapify_down` to restore the heap property.
Examples
So far, we have explained everything about heap data structure. We discussed its operations also, and now we will see its code implementation in different languages :
Java
import java.util.PriorityQueue;
import java.util.Collections;
public class HeapExample {
public static void main(String[] args) {
// Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(30);
minHeap.add(20);
System.out.print("Min Heap Contents: ");
printHeap(minHeap);
System.out.println("Smallest element removed from Min Heap: " + minHeap.poll());
System.out.print("Min Heap after polling: ");
printHeap(minHeap);
// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(10);
maxHeap.add(30);
maxHeap.add(20);
System.out.print("Max Heap Contents: ");
printHeap(maxHeap);
System.out.println("Largest element removed from Max Heap: " + maxHeap.poll());
System.out.print("Max Heap after polling: ");
printHeap(maxHeap);
}
private static void printHeap(PriorityQueue<Integer> heap) {
PriorityQueue<Integer> tempHeap = new PriorityQueue<>(heap);
while (!tempHeap.isEmpty()) {
System.out.print(tempHeap.poll() + " ");
}
System.out.println();
}
}
You can also try this code with Online Java Compiler
C++
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
void printHeap(std::priority_queue<int, std::vector<int>, std::greater<int>> heap) {
while (!heap.empty()) {
std::cout << heap.top() << " ";
heap.pop();
}
std::cout << std::endl;
}
void printHeap(std::priority_queue<int> heap) {
while (!heap.empty()) {
std::cout << heap.top() << " ";
heap.pop();
}
std::cout << std::endl;
}
int main() {
// Min Heap
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
std::cout << "Min Heap Contents: ";
printHeap(minHeap);
std::cout << "Smallest element removed from Min Heap: " << minHeap.top() << std::endl;
minHeap.pop();
std::cout << "Min Heap after polling: ";
printHeap(minHeap);
// Max Heap
std::priority_queue<int> maxHeap;
maxHeap.push(10);
maxHeap.push(30);
maxHeap.push(20);
std::cout << "Max Heap Contents: ";
printHeap(maxHeap);
std::cout << "Largest element removed from Max Heap: " << maxHeap.top() << std::endl;
maxHeap.pop();
std::cout << "Max Heap after polling: ";
printHeap(maxHeap);
}
You can also try this code with Online C++ Compiler
Python
import heapq
def print_heap(heap):
# Create a copy of the heap so original heap isn't modified
copy = heap[:]
result = []
while copy:
result.append(heapq.heappop(copy))
print(" ".join(map(str, result)))
def main():
# Min Heap
min_heap = []
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 30)
heapq.heappush(min_heap, 20)
print("Min Heap Contents: ")
print_heap(min_heap)
print("Smallest element removed from Min Heap: ", heapq.heappop(min_heap))
print("Min Heap after polling: ")
print_heap(min_heap) # Show remaining elements
# Max Heap using negative values
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -20)
print("Max Heap Contents: ")
print_heap([-x for x in max_heap]) # Convert back to positive for printing
print("Largest element removed from Max Heap: ", -heapq.heappop(max_heap))
print("Max Heap after polling: ")
print_heap([-x for x in max_heap]) # Show remaining elements
if __name__ == "__main__":
main()
You can also try this code with Online Python Compiler
Output
Min Heap Contents: 10 20 30
Smallest element removed from Min Heap: 10
Min Heap after polling: 20 30
Max Heap Contents: 30 20 10
Largest element removed from Max Heap: 30
Max Heap after polling: 20 10
Frequently Asked Questions
What is the time complexity of inserting an element into a heap?
The time complexity of inserting an element into a heap is O(log n), where n is the number of elements in the heap.
Can a heap contain duplicate elements?
Yes, a heap can contain duplicate elements. The heap property is maintained based on the value of the elements, not their uniqueness.
What is the difference between a heap & a binary search tree?
While both heaps & binary search trees are tree-based data structures, a heap maintains the heap property (the parent is always greater than or equal to/less than or equal to the children) whereas a binary search tree maintains the binary search tree property (the left subtree of a node contains only nodes with keys less than the node's key, & the right subtree contains only nodes with keys greater than the node's key).
Conclusion
In this article, we have learned about the heap data structure, a special type of binary tree where the tree is a complete binary tree & fulfills the heap in java. We discussed the two types of heaps (max heap & min heap), the basic operations on heaps (insertion & deletion), & some common applications of heaps such as heap sort, priority queues, & graph algorithms. We also looked at the algorithms for insertion and deletion and lastly, we saw code examples of implementation in different languages.
34+ registered 
