Max Heap
Definition
A Max Heap is a specific type of heap where the value of every “parent” node is greater than or equal to the values of its “children.” This means the largest number is always sitting at the top (the root).
How it Works
- The Rule: If you look at any node in the tree, it must be larger than the nodes below it.
- Insertion: When you add a new number, you add it to the bottom-leftmost open spot. Then you “bubble it up” (swap it with its parent) until the rule is satisfied.
- Extraction: When you remove the max element (the root), you replace it with the last element in the tree and “bubble it down” (swap with the largest child) to restore the order.
Example
Input Numbers: [10, 20, 15, 30, 40] Max Heap Structure: 40 / \ 30 15 / \ 10 20 Notice that 40 is bigger than its children (30 and 15), and 30 is bigger than its children (10 and 20).
Code Example:
PythonJavaCC++
import heapq
# Python's heapq module implements a Min Heap by default.
# To create a Max Heap, we invert values using negative numbers.
numbers = [10, 20, 15, 30, 40]
max_heap = []
# Insert elements
for num in numbers:
heapq.heappush(max_heap, -num) # store negative value
# Max element (convert back to positive)
print("Max value:", -max_heap[0]) # 40
# Remove max element
largest = -heapq.heappop(max_heap)
print("Removed:", largest) # 40
import java.util.PriorityQueue;
import java.util.Collections;
public class MaxHeapExample {
public static void main(String[] args) {
// Java PriorityQueue default = Min Heap
// Use reverseOrder() to create Max Heap
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Collections.reverseOrder());
int[] numbers = {10, 20, 15, 30, 40};
// Insert elements
for (int num : numbers) {
maxHeap.add(num);
}
// Print max element
System.out.println("Max value: " + maxHeap.peek()); // 40
// Remove max element
int largest = maxHeap.poll();
System.out.println("Removed: " + largest); // 40
}
}
#include <stdio.h>
#define SIZE 100
int heap[SIZE];
int n = 0;
// Insert into Max Heap
void insert(int value) {
int i = n++;
heap[i] = value;
// Heapify up
while (i != 0 && heap[(i - 1) / 2] < heap[i]) {
int temp = heap[i];
heap[i] = heap[(i - 1) / 2];
heap[(i - 1) / 2] = temp;
i = (i - 1) / 2;
}
}
// Remove max element
int extractMax() {
int root = heap[0];
heap[0] = heap[--n];
int i = 0;
while (1) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < n && heap[left] > heap[largest])
largest = left;
if (right < n && heap[right] > heap[largest])
largest = right;
if (largest != i) {
int temp = heap[i];
heap[i] = heap[largest];
heap[largest] = temp;
i = largest;
}
else
break;
}
return root;
}
int main() {
int numbers[] = {10,20,15,30,40};
for (int i = 0; i < 5; i++)
insert(numbers[i]);
printf("Max value: %d\n", heap[0]);
int largest = extractMax();
printf("Removed: %d\n", largest);
return 0;
}
#include <iostream>
#include <queue>
using namespace std;
int main() {
// C++ priority_queue = Max Heap by default
priority_queue<int> maxHeap;
int numbers[] = {10,20,15,30,40};
for (int i = 0; i < 5; i++)
maxHeap.push(numbers[i]);
cout << "Max value: " << maxHeap.top() << endl;
int largest = maxHeap.top();
maxHeap.pop();
cout << "Removed: " << largest << endl;
return 0;
}
Use Cases & Interview Relevance
- Finding the Kth Smallest Element: Often used to efficiently manage sets of data where you need quick access to the largest item.
- Memory Management: The Java Garbage Collector often uses similar structures to manage memory blocks.