HeapProblem 1 of 18
Implement a Maxheap MinHeap using arrays and recursion
Problem Statement
Implement a Max-Heap and Min-Heap data structure using arrays and recursion. The heap should support the following operations:
- Insert: Add a new element to the heap
- Extract Max/Min: Remove and return the maximum/minimum element
- Heapify: Convert an array into a valid heap
Example:
- Input: Insert elements
[3, 1, 6, 5, 2, 4]into a Max-Heap - Output Max-Heap Array:
[6, 5, 4, 1, 2, 3] - Extract Max: Returns
6, heap becomes[5, 3, 4, 1, 2]
Approach 1: Top-Down Insertion (Brute Force)
Intuition
Insert elements one by one at the end of the array and bubble up to maintain the heap property. This is straightforward but takes O(n log n) for building the heap.
Algorithm
- Insert element at the end of the array
- Compare with parent and swap if heap property is violated
- Repeat until the element reaches its correct position or becomes root
- For extraction, swap root with last element, remove last, and heapify down
java
import java.util.ArrayList;
class MaxHeap {
private ArrayList<Integer> heap;
public MaxHeap() {
heap = new ArrayList<>();
}
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
private void heapifyUp(int i) {
if (i == 0) return;
if (heap.get(parent(i)) < heap.get(i)) {
swap(parent(i), i);
heapifyUp(parent(i));
}
}
private void heapifyDown(int i) {
int largest = i;
int left = leftChild(i);
int right = rightChild(i);
int n = heap.size();
if (left < n && heap.get(left) > heap.get(largest)) {
largest = left;
}
if (right < n && heap.get(right) > heap.get(largest)) {
largest = right;
}
if (largest != i) {
swap(i, largest);
heapifyDown(largest);
}
}
public void insert(int val) {
heap.add(val);
heapifyUp(heap.size() - 1);
}
public int extractMax() {
if (heap.isEmpty()) return -1;
int maxVal = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heapifyDown(0);
}
return maxVal;
}
public int getMax() {
return heap.isEmpty() ? -1 : heap.get(0);
}
}
class MinHeap {
private ArrayList<Integer> heap;
public MinHeap() {
heap = new ArrayList<>();
}
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
private void heapifyUp(int i) {
if (i == 0) return;
if (heap.get(parent(i)) > heap.get(i)) {
swap(parent(i), i);
heapifyUp(parent(i));
}
}
private void heapifyDown(int i) {
int smallest = i;
int left = leftChild(i);
int right = rightChild(i);
int n = heap.size();
if (left < n && heap.get(left) < heap.get(smallest)) {
smallest = left;
}
if (right < n && heap.get(right) < heap.get(smallest)) {
smallest = right;
}
if (smallest != i) {
swap(i, smallest);
heapifyDown(smallest);
}
}
public void insert(int val) {
heap.add(val);
heapifyUp(heap.size() - 1);
}
public int extractMin() {
if (heap.isEmpty()) return -1;
int minVal = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heapifyDown(0);
}
return minVal;
}
public int getMin() {
return heap.isEmpty() ? -1 : heap.get(0);
}
}Complexity Analysis
- Time Complexity: O(log n) per insertion, O(n log n) to build heap from n elements
- Space Complexity: O(n) for storing n elements
Approach 2: Bottom-Up Heapify (Optimal)
Intuition
Build the heap from an existing array using bottom-up heapify. Start from the last non-leaf node and heapify down. This achieves O(n) time complexity due to the mathematical property that most nodes are near the bottom with small heights.
Algorithm
- Given an array, start from the last non-leaf node (index n/2 - 1)
- Apply heapifyDown on each node moving towards the root
- This ensures all subtrees satisfy heap property
- Total work done is O(n) due to height distribution
java
import java.util.ArrayList;
import java.util.List;
class MaxHeap {
private ArrayList<Integer> heap;
public MaxHeap() {
heap = new ArrayList<>();
}
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
private void heapifyDown(int i) {
int largest = i;
int left = leftChild(i);
int right = rightChild(i);
int n = heap.size();
if (left < n && heap.get(left) > heap.get(largest)) {
largest = left;
}
if (right < n && heap.get(right) > heap.get(largest)) {
largest = right;
}
if (largest != i) {
swap(i, largest);
heapifyDown(largest);
}
}
private void heapifyUp(int i) {
if (i == 0) return;
if (heap.get(parent(i)) < heap.get(i)) {
swap(parent(i), i);
heapifyUp(parent(i));
}
}
// Build heap from array in O(n)
public void buildHeap(int[] arr) {
heap.clear();
for (int val : arr) {
heap.add(val);
}
int n = heap.size();
// Start from last non-leaf node
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyDown(i);
}
}
public void insert(int val) {
heap.add(val);
heapifyUp(heap.size() - 1);
}
public int extractMax() {
if (heap.isEmpty()) return -1;
int maxVal = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heapifyDown(0);
}
return maxVal;
}
public int getMax() {
return heap.isEmpty() ? -1 : heap.get(0);
}
public boolean isEmpty() { return heap.isEmpty(); }
public int size() { return heap.size(); }
}
class MinHeap {
private ArrayList<Integer> heap;
public MinHeap() {
heap = new ArrayList<>();
}
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
private void heapifyDown(int i) {
int smallest = i;
int left = leftChild(i);
int right = rightChild(i);
int n = heap.size();
if (left < n && heap.get(left) < heap.get(smallest)) {
smallest = left;
}
if (right < n && heap.get(right) < heap.get(smallest)) {
smallest = right;
}
if (smallest != i) {
swap(i, smallest);
heapifyDown(smallest);
}
}
private void heapifyUp(int i) {
if (i == 0) return;
if (heap.get(parent(i)) > heap.get(i)) {
swap(parent(i), i);
heapifyUp(parent(i));
}
}
// Build heap from array in O(n)
public void buildHeap(int[] arr) {
heap.clear();
for (int val : arr) {
heap.add(val);
}
int n = heap.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyDown(i);
}
}
public void insert(int val) {
heap.add(val);
heapifyUp(heap.size() - 1);
}
public int extractMin() {
if (heap.isEmpty()) return -1;
int minVal = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heapifyDown(0);
}
return minVal;
}
public int getMin() {
return heap.isEmpty() ? -1 : heap.get(0);
}
public boolean isEmpty() { return heap.isEmpty(); }
public int size() { return heap.size(); }
}Complexity Analysis
- Time Complexity: O(n) for building heap, O(log n) for insert/extract
- Space Complexity: O(n) for storing n elements
Key Takeaways
- Array Representation: For node at index i: parent = (i-1)/2, left child = 2i+1, right child = 2i+2
- Bottom-up build is O(n) vs top-down insertion which is O(n log n)
- HeapifyUp is used after insertion to maintain heap property
- HeapifyDown is used after extraction and during heap building
- Max-Heap: Parent >= children, Min-Heap: Parent <= children
- Recursive implementations are cleaner but iterative versions save stack space