WikiGalaxy
Max Heap Introduction
Definition
A Max Heap is a complete binary tree where the value of each node is greater than or equal to the values of its children. This structure ensures that the largest element is always at the root.
Heap Property
Heap Order Property
In a Max Heap, for any given node I, the value of I is greater than or equal to the values of its children. This property must be recursively true for all nodes in the heap.
Applications of Max Heap
Priority Queues
Max Heaps are commonly used to implement priority queues, where the highest priority element is always at the front.
Heap Sort
Heap Sort is an efficient sorting algorithm that uses the heap data structure to sort elements in O(n log n) time.
Building a Max Heap
Bottom-Up Approach
The bottom-up approach involves starting from the last non-leaf node and adjusting the heap property upwards. This is more efficient than inserting elements one by one.
public void buildMaxHeap(int[] array) {
for (int i = array.length / 2 - 1; i >= 0; i--) {
heapify(array, array.length, i);
}
}
Max Heap Operations
Insertion
To insert a new element, add it to the end of the heap and then restore the heap property by comparing it with its parent and swapping if necessary.
public void insert(int[] heap, int value) {
heap[++heapSize] = value;
int current = heapSize;
while (heap[current] > heap[parent(current)]) {
swap(heap, current, parent(current));
current = parent(current);
}
}
Extracting Maximum
Extract-Max Operation
The extract-max operation removes the largest element from the heap (the root), replaces it with the last element, and then restores the heap property.
public int extractMax(int[] heap) {
int max = heap[0];
heap[0] = heap[heapSize--];
heapify(heap, heapSize, 0);
return max;
}
Heapify Process
Heapify Function
Heapify is a recursive process used to maintain the heap property. It compares a node with its children and swaps them if necessary, continuing the process down the tree.
private void heapify(int[] array, int size, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && array[left] > array[largest]) {
largest = left;
}
if (right < size && array[right] > array[largest]) {
largest = right;
}
if (largest != i) {
swap(array, i, largest);
heapify(array, size, largest);
}
}
Max Heap Use Case
Real-Time Scheduling
Max Heaps are used in real-time scheduling systems to manage tasks based on priority, ensuring that the highest priority task is executed first.
