Min and Max Heaps are specialized binary tree structures that play a crucial role in algorithms and data structure optimization, especially in the realm of priority queues and scheduling algorithms. Before diving into the specifics of Min and Max Heaps, let’s revisit some fundamental concepts.
Binary Tree Basics
A Binary Tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. This structure is characterized by the following:
- Reference to the left child
- Reference to the right child
- Data stored within the node
A complete Binary Tree is a specific type of binary tree where all levels, except possibly the last, are fully filled, and all nodes are as far left as possible.
Min-Heap and Max-Heap
Both Min-Heaps and Max-Heaps are complete binary trees, but they differ in how they order the elements:
Min-Heap
- The root node contains the minimum value.
- Every node’s value is greater than or equal to its parent’s value.
- It ensures that the minimum value can be accessed in constant time.
Max-Heap
- The root node contains the maximum value.
- Every node’s value is less than or equal to its parent’s value.
- It ensures that the maximum value can be accessed in constant time.
Representation
Min/Max heaps are efficiently represented using arrays due to their complete binary tree structure. The array representation follows these rules:
Arr[0]contains the root node.Arr[(i-1)/2]returns the parent node of thei-thnode.Arr[(2*i)+1]returns the left child node.Arr[(2*i)+2]returns the right child node.
Time Complexity Overview
- Get Max or Min Element: O(1), as the element is always at the root.
- Remove Max or Min Element: O(Log n), due to the need to reheapify the tree to maintain heap properties.
- Insert an Element: O(Log n), as the element is inserted at the end, and the tree is then reheapified.
Complete Code Example: Implementing a Min Heap
Below is a simple Java implementation of a Min Heap to illustrate these concepts:
public class MinHeap {
private int[] heap;
private int size;
private int capacity;
public MinHeap(int capacity) {
this.capacity = capacity;
this.heap = new int[capacity];
this.size = 0;
}
private int getParentIndex(int i) { return (i - 1) / 2; }
private int getLeftChildIndex(int i) { return 2 * i + 1; }
private int getRightChildIndex(int i) { return 2 * i + 2; }
public void insert(int element) {
// Ensure there's enough capacity in the heap before inserting a new element
ensureExtraCapacity();
heap[size] = element; // Place the new element at the end of the heap
int current = size; // Index of the newly added element
size++; // Increase the size of the heap
// Heapify up: While the newly added element is smaller than its parent, swap them
while (heap[current] < heap[getParentIndex(current)]) {
swap(current, getParentIndex(current));
current = getParentIndex(current); // Move up to the parent
}
}
private void ensureExtraCapacity() {
if (size == capacity) {
int[] newHeap = new int[capacity * 2]; // Double the capacity
for (int i = 0; i < heap.length; i++) {
newHeap[i] = heap[i]; // Copy existing elements to the new array
}
heap = newHeap; // Replace the old heap array with the new array
capacity *= 2; // Update the capacity
}
}
public int remove() {
if (size == 0) throw new IllegalStateException("Heap is empty");
int popped = heap[0];
heap[0] = heap[--size];
minHeapify(0);
return popped;
}
private void minHeapify(int i) {
int left = getLeftChildIndex(i);
int right = getRightChildIndex(i);
int smallest = i;
if (left < size && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < size && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != i) {
swap(i, smallest);
minHeapify(smallest);
}
}
public void heapSort() {
// Build the min heap
for (int i = size / 2 - 1; i >= 0; i--) {
minHeapify(i);
}
// Extract elements from the heap one by one
for (int i = size - 1; i >= 0; i--) {
// Move current root to end (since it's the smallest)
swap(0, i);
// call min heapify on the reduced heap
size--; // Reduce the size of the heap
minHeapify(0);
}
}
private void swap(int x, int y) {
int temp = heap[x];
heap[x] = heap[y];
heap[y] = temp;
}
// Method to print the contents of the heap
public void printHeap() {
for (int i = 0; i < size / 2; i++) {
System.out.print(" PARENT : " + heap[i]);
if (getLeftChildIndex(i) < size) // Checking if left child exists
System.out.print(" LEFT CHILD : " + heap[getLeftChildIndex(i)]);
if (getRightChildIndex(i) < size) // Checking if right child exists
System.out.print(" RIGHT CHILD :" + heap[getRightChildIndex(i)]);
System.out.println();
}
}
}
This class provides the basic functionality to insert elements into a Min Heap and remove the minimum element, demonstrating the practical application of the concepts discussed.
Java implementation of a Max Heap.
This implementation is similar to the Min Heap, but with the key difference being in the heap property— in a Max Heap, each parent node is greater than or equal to its child nodes. This ensures the maximum element is always at the root of the heap.
public class MaxHeap {
private int[] heap;
private int size;
private int capacity;
public MaxHeap(int capacity) {
this.capacity = capacity;
this.heap = new int[capacity];
this.size = 0;
}
private int getParentIndex(int i) { return (i - 1) / 2; }
private int getLeftChildIndex(int i) { return 2 * i + 1; }
private int getRightChildIndex(int i) { return 2 * i + 2; }
public void insert(int element) {
if (size == capacity) throw new IllegalStateException("Heap is full");
heap[size] = element;
int current = size;
size++;
// Heapify up
while (heap[current] > heap[getParentIndex(current)]) {
swap(current, getParentIndex(current));
current = getParentIndex(current);
}
}
public int remove() {
if (size == 0) throw new IllegalStateException("Heap is empty");
int popped = heap[0];
heap[0] = heap[--size];
maxHeapify(0);
return popped;
}
private void maxHeapify(int i) {
int left = getLeftChildIndex(i);
int right = getRightChildIndex(i);
int largest = i;
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
if (largest != i) {
swap(i, largest);
maxHeapify(largest);
}
}
private void swap(int x, int y) {
int temp = heap[x];
heap[x] = heap[y];
heap[y] = temp;
}
public void heapSort() {
// Build the max heap
for (int i = size / 2 - 1; i >= 0; i--) {
maxHeapify(i);
}
// Extract elements from the heap one by one
for (int i = size - 1; i >= 0; i--) {
// Move current root to end (since it's the largest)
swap(0, i);
// Call max heapify on the reduced heap
size--; // Reduce the size of the heap for heapify
maxHeapify(0);
}
}
// Method to print the contents of the heap
public void printHeap() {
for (int i = 0; i < size / 2; i++) {
System.out.print(" PARENT : " + heap[i]);
if (getLeftChildIndex(i) < size) // Checking if left child exists
System.out.print(" LEFT CHILD : " + heap[getLeftChildIndex(i)]);
if (getRightChildIndex(i) < size) // Checking if right child exists
System.out.print(" RIGHT CHILD :" + heap[getRightChildIndex(i)]);
System.out.println();
}
}
// Main method to test
public static void main(String[] arg) {
MaxHeap maxHeap = new MaxHeap(15);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(17);
maxHeap.insert(10);
maxHeap.insert(84);
maxHeap.insert(19);
maxHeap.insert(6);
maxHeap.insert(22);
maxHeap.insert(9);
System.out.println("The Max Heap is ");
maxHeap.printHeap();
System.out.println("The max val is " + maxHeap.remove());
System.out.println("Sorted array is:");
maxHeap.heapSort();
}}
This MaxHeap class includes basic operations such as insert (to add a new element to the heap) and remove (to remove and return the maximum element from the heap). The maxHeapify method is used to maintain the heap property after the removal of the root element, and during the insertion process, the heapify up process ensures that the heap property is preserved as elements are added.
The printHeap method is a utility function that prints the heap in a readable format, showing each parent node and its children, which can be helpful for debugging or understanding the heap’s structure visually.
Remember, the key aspect of a Max Heap is that the parent node is always greater than or equal to its children, which ensures that the maximum value is always at the root of the heap, allowing for constant time retrieval of the maximum element.
Conclusion
Understanding Min Heaps and Max Heaps is fundamental for anyone looking to enhance their problem-solving skills in data structures and algorithms. These structures are pivotal in numerous applications, including priority queues, scheduling algorithms, and the efficient implementation of graph algorithms. By mastering heaps
