Min Heap and Max Heap

A max heap has the biggest number at the top and a min heap has the smallest, like two different pyramids of prizes for the tallest or the shortest kid.

In this page:

Max Heap
Min Heap
Root Element
Compare Heaps
Practice

Syntax

markup

import heapq
min_heap = []
heapq.heappush(min_heap, value)
smallest = heapq.heappop(min_heap)

# max heap: store negated values
heapq.heappush(max_heap, -value)

Max Heap

In a max heap, every parent node's value is greater than or equal to both of its children's values, which recursively guarantees the single largest value in the entire structure sits at the root.

Example: Max Heap

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> maxHeap;
    maxHeap.push(10); maxHeap.push(30); maxHeap.push(20);
    cout << "Max heap top: " << maxHeap.top() << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(10); maxHeap.add(30); maxHeap.add(20);
        System.out.println("Max heap top: " + maxHeap.peek());
    }
}

import heapq
max_heap = []
for v in [10, 30, 20]:
    heapq.heappush(max_heap, -v)
print("Max heap top:", -max_heap[0])

#include <stdio.h>
int main() {
    int heap[] = {30, 10, 20};
    printf("Max heap top: %d\n", heap[0]);
    return 0;
}

Min Heap

In a min heap, every parent node's value is smaller than or equal to both of its children's values, which recursively guarantees the single smallest value in the entire structure sits at the root.

Example: Min Heap

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(10); minHeap.push(30); minHeap.push(20);
    cout << "Min heap top: " << minHeap.top() << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(10); minHeap.add(30); minHeap.add(20);
        System.out.println("Min heap top: " + minHeap.peek());
    }
}

import heapq
min_heap = []
for v in [10, 30, 20]:
    heapq.heappush(min_heap, v)
print("Min heap top:", min_heap[0])

#include <stdio.h>
int main() {
    int heap[] = {10, 30, 20};
    printf("Min heap top: %d\n", heap[0]);
    return 0;
}

Root Element

Because of these properties, the root always gives immediate access to the current highest-priority element in a max heap, or the current lowest-priority element in a min heap, without needing to scan any other part of the structure.

Example: Root Element

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> maxHeap;
    maxHeap.push(5); maxHeap.push(15);
    cout << "Root gives O(1) access to highest priority: " << maxHeap.top() << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(5); maxHeap.add(15);
        System.out.println("Root gives O(1) access to highest priority: " + maxHeap.peek());
    }
}

import heapq
max_heap = []
for v in [5, 15]:
    heapq.heappush(max_heap, -v)
print("Root gives O(1) access to highest priority:", -max_heap[0])

#include <stdio.h>
int main() {
    int heap[] = {15, 5};
    printf("Root gives O(1) access to highest priority: %d\n", heap[0]);
    return 0;
}

Compare Heaps

The two heap types are structurally identical — same complete binary tree, same array storage, same parent/child index formulas — differing only in the direction of the comparison used to maintain the heap property during insertions and removals.

Example: Compare Heaps

#include <iostream>
using namespace std;
int main() {
    cout << "Same structure and formulas, only the comparison direction differs (>= for max, <= for min)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Same structure and formulas, only the comparison direction differs (>= for max, <= for min)");
    }
}

print("Same structure and formulas, only the comparison direction differs (>= for max, <= for min)")

#include <stdio.h>
int main() {
    printf("Same structure and formulas, only the comparison direction differs (>= for max, <= for min)\n");
    return 0;
}

Practice

Building both a max heap and a min heap from the same set of values and comparing their resulting shapes side by side is a quick way to see that the values end up in genuinely different tree arrangements despite using an identical structure.

Example: Practice

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int v : {4, 9, 1, 7}) { maxHeap.push(v); minHeap.push(v); }
    cout << "Same input, max top=" << maxHeap.top() << " min top=" << minHeap.top() << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int v : new int[]{4,9,1,7}) { maxHeap.add(v); minHeap.add(v); }
        System.out.println("Same input, max top=" + maxHeap.peek() + " min top=" + minHeap.peek());
    }
}

import heapq
values = [4, 9, 1, 7]
max_heap = []
min_heap = []
for v in values:
    heapq.heappush(max_heap, -v)
    heapq.heappush(min_heap, v)
print("Same input, max top=", -max_heap[0], "min top=", min_heap[0])

#include <stdio.h>
int main() {
    int values[] = {4,9,1,7};
    int maxV = values[0], minV = values[0];
    for (int i=1;i<4;i++){ if(values[i]>maxV) maxV=values[i]; if(values[i]<minV) minV=values[i]; }
    printf("Same input, max top=%d min top=%d\n", maxV, minV);
    return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Heap Introduction Next Lesson → Heap Sort