A min heap is a type of data structure that is used in a variety of applications such as priority queues, heapsort, and more. It is a complete binary tree that follows the heap property, which states that the value of any node is greater than or equal to the value of its parent node. In this article, we will discuss the features of a min heap, and how it works. We will also discuss the time and space complexities for insertion, deletion, access and search, and provide several Java code examples to illustrate each operation. Lastly, we will provide several coding exercises with solutions to test the reader’s understanding of min heaps.
What is a Min Heap?
A min heap is a type of binary tree. It is a complete binary tree, meaning that all levels of the tree are filled except for possibly the last level, which is filled from left to right. The heap property states that the value of any node is greater than or equal to the value of its parent node. In a min heap, this means that the root node has the smallest value in the tree.
The main operations with a min heap are insertion, deletion, and search. Insertion adds a new item to the heap, while deletion removes an item from the heap. Search finds an item in the heap. All of these operations can be performed in time proportional to the height of the tree, which is log n, where n is the number of items in the tree.
Time Complexity
When using a min heap, the time complexity for insertion, deletion, access, and search will all depend on the height of the tree, which is log n, where n is the number of items in the tree. The time complexity for insertion and deletion is O(log n), while the time complexity for access and search is O(1).
Space Complexity
The space complexity for a min heap is O(n), where n is the number of items in the tree. This is because each node in the tree requires a certain amount of space to store its data.
Java Code Examples
Now that we have discussed the features of a min heap and the time and space complexities for the operations, let’s look at some Java code examples to illustrate each operation.
Insertion
To insert an item into a min heap, we first need to find the appropriate location for the item. This can be done by comparing the value of the item with the value of its parent node. If the value of the item is smaller than the value of its parent node, then we can insert the item into the heap.
public void insert(int item) {
// Get the size of the heap
int n = heap.size();
// Add the item to the end of the heap
heap.add(item);
// Compare the item to its parent node
int i = n;
int parent = (i-1)/2;
// If the item is smaller than its parent, swap them
while (i > 0 && heap.get(i) < heap.get(parent)) {
int temp = heap.get(i);
heap.set(i, heap.get(parent));
heap.set(parent, temp);
i = parent;
parent = (i-1)/2;
}
}
Deletion
Deletion is the process of removing an item from the heap. To do this, we first need to find the item we want to remove. Once the item is found, we need to replace it with the last item in the heap. Then, we need to compare the new item with its parent and children nodes and swap it with the smallest item.
public void delete(int item) {
// Get the size of the heap
int n = heap.size();
// Find the item we want to delete
int i = 0;
for (int j = 0; j < n; j++) {
if (heap.get(j) == item) {
i = j;
break;
}
}
// Replace the item with the last item in the heap
heap.set(i, heap.get(n-1));
heap.remove(n-1);
n--;
// Compare the item to its parent and children nodes
int parent = (i-1)/2;
int left = 2*i + 1;
int right = 2*i + 2;
// Swap the item with the smallest item
while (i > 0 && heap.get(i) < heap.get(parent)) {
int temp = heap.get(i);
heap.set(i, heap.get(parent));
heap.set(parent, temp);
i = parent;
parent = (i-1)/2;
}
while (left < n && (heap.get(i) > heap.get(left) ||
heap.get(i) > heap.get(right))) {
if (heap.get(left) < heap.get(right)) {
int temp = heap.get(i);
heap.set(i, heap.get(left));
heap.set(left, temp);
i = left;
}
else {
int temp = heap.get(i);
heap.set(i, heap.get(right));
heap.set(right, temp);
i = right;
}
left = 2*i + 1;
right = 2*i + 2;
}
}
Access
Access is the process of retrieving an item from the heap. To do this, we simply need to retrieve the item at the root node. This operation can be done in constant time, as the root node is always the smallest item in the heap.
public int access() {
return heap.get(0);
}
Search
Search is the process of finding an item in the heap. To do this, we need to traverse the heap, comparing each item to the item we are looking for. This operation can also be done in constant time, as the root node is always the smallest item in the heap.
public int search(int item) {
// Traverse the heap, comparing each item to the item we are looking for
for (int i = 0; i < heap.size(); i++) {
if (heap.get(i) == item) {
return i;
}
}
// If the item is not found, return -1
return -1;
}
Conclusion
In this article, we have discussed the features of a min heap, how it works, and the time and space complexities for the operations. We have also provided Java code examples to illustrate each operation. A min heap is a type of binary tree that follows the heap property, which states that the value of any node is greater than or equal to the value of its parent node. The operations with a min heap are insertion, deletion, and search, and all of these operations can be performed in time proportional to the height of the tree, which is log n, where n is the number of items in the tree. The space complexity for a min heap is O(n), where n is the number of items in the tree.
Exercises
Given a min heap, write a function to delete the root node.
public void deleteRoot() {
// Get the size of the heap
int n = heap.size();
// Replace the root node with the last item in the heap
heap.set(0, heap.get(n-1));
heap.remove(n-1);
n--;
// Compare the root node to its parent and children nodes
int i = 0;
int parent = (i-1)/2;
int left = 2*i + 1;
int right = 2*i + 2;
// Swap the root node with the smallest item
while (i > 0 && heap.get(i) < heap.get(parent)) {
int temp = heap.get(i);
heap.set(i, heap.get(parent));
heap.set(parent, temp);
i = parent;
parent = (i-1)/2;
}
while (left < n && (heap.get(i) > heap.get(left) ||
heap.get(i) > heap.get(right))) {
if (heap.get(left) < heap.get(right)) {
int temp = heap.get(i);
heap.set(i, heap.get(left));
heap.set(left, temp);
i = left;
}
else {
int temp = heap.get(i);
heap.set(i, heap.get(right));
heap.set(right, temp);
i = right;
}
left = 2*i + 1;
right = 2*i + 2;
}
}
Given a min heap, write a function to find the minimum item in the heap.
public int findMin() {
return heap.get(0);
}
Given a min heap, write a function to find the maximum item in the heap.
public int findMax() {
// Get the size of the heap
int n = heap.size();
// Initialize the max to the first item in the heap
int max = heap.get(0);
// Traverse the heap, comparing each item to the max
for (int i = 1; i < n; i++) {
if (heap.get(i) > max) {
max = heap.get(i);
}
}
return max;
}
Given a min heap, write a function to find the height of the heap.
public int findHeight() {
// Get the size of the heap
int n = heap.size();
// Initialize the height to 0
int height = 0;
// Traverse the heap, increasing the height each time
// we reach a new level
int i = 0;
while (i < n) {
height++;
i = 2*i + 1;
}
return height;
}
Given a min heap, write a function to print it out in level order.
public void printLevelOrder() {
// Get the size of the heap
int n = heap.size();
// Initialize the level to 0
int level = 0;
// Traverse the heap, printing each item at the current level
int i = 0;
while (i < n) {
System.out.print(heap.get(i) + " ");
i++;
if (i == Math.pow(2, level)) {
System.out.println();
level++;
}
}
}