Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in C++

What Is a Max Heap?

Explore the concept of a max heap, a complete binary tree with the largest element at the root. Learn how to perform key operations such as insert, extract max, peek, and check heap status, along with their time complexities. Understand when to use max heaps for tasks requiring quick access to the largest elements, including priority queues and heap sort.

We'll cover the following...

Max heap

A max heap is a complete binary tree where every parent node is greater than or equal to its children. This means the largest element in the entire heap is always sitting at the root, making it instantly accessible at any time.

Example: Consider a max heap containing the values 14, 10, 8, 5, 2.

Visualization of a max heap
Visualization of a max heap

The root is 14 because it is the largest element. Its children are 10 and 8, both of whom are less than 14. Similarly, 10's children are 5 and 2, both of whom are less than 10. This ordering holds at every level of the tree, which makes it a valid max heap.

In array form, this heap is stored as [14, 10, 8, 5, 2], with the root at index 0.

Key operations on a max heap

Now that we understand what a max heap is, let's explore the fundamental operations that allow us to interact with it. These operations define what makes a max heap useful and how we manipulate the data it holds.

The isEmpty operation

The isEmpty operation returns true if the heap is empty. This is crucial before attempting to remove or view elements, as attempting to extract from an empty heap results in an error.

Example: Consider a max heap that currently holds [14, 10, 8, 5, 2]. The size is 5. Calling isEmpty() on this heap would return False because size is 5, not 0.

If we were to extract the maximum one by one until no elements remain, size would eventually become 0. At that point, calling isEmpty() would return True.

C++ implementation

In an array-based max heap, we check if size equals 0. We initialized size to 0 when creating an empty heap, so if it is still 0, no elements have been added.

C++ 17
#include <iostream>
#include <vector>
using namespace std;
class MaxHeap {
public:
    int capacity;              // Maximum number of elements
    vector<int> data;          // Array to store elements
    int size;                  // Current number of elements
    // Initialize an empty max heap with given capacity
    MaxHeap(int capacity = 10) {
        this->capacity = capacity;
        data.resize(capacity);
        size = 0;
    }
    bool isEmpty() {
        // Check if the heap is empty
        return size == 0;
    }
};
int main() {
    // Create a max heap
    MaxHeap heap(10);
    cout << "Is heap empty? "
         << (heap.isEmpty() ? "true" : "false")
         << endl;
    // Output: true (heap is empty)
    return 0;
}

The isFull operation

The isFull operation checks whether the heap has reached its maximum capacity. This is only relevant for array-based heaps with a fixed size. Before inserting a new element, we should check if there is space available.

Example: Consider a max heap with capacity 5 that currently holds [14, 10, 8, 5, 2]. The size is 5 and the capacity is 5. Since size equals capacity, the heap is full. Calling isFull() would return True.

If we extract the maximum element (14), size would become 4. Now size (4) is less than capacity (5), so calling isFull() would return False.

C++ implementation

In an array-based max heap, we check if size equals capacity. If size has reached the capacity, then the heap is full, so we return True.

C++ 17
#include <iostream>
#include <vector>
using namespace std;
class MaxHeap {
public:
    int capacity;              // Maximum number of elements
    vector<int> data;          // Array to store elements
    int size;                  // Current number of elements
    MaxHeap(int capacity = 10) {
        this->capacity = capacity;
        data.resize(capacity);
        size = 0;
    }
    bool isEmpty() {
        return size == 0;
    }
    bool isFull() {
        // Check if the heap is full
        return size == capacity;
    }
};
int main() {
    // Create a max heap with capacity 5
    MaxHeap heap(5);
    // Simulate a full heap with elements: [14, 10, 8, 5, 2]
    heap.size = 5;
    cout << "Is heap full? "
         << (heap.isFull() ? "true" : "false")
         << endl;
    // Output: true (heap is full)
    cout << "Simulating extracting one element from the heap"
         << endl;
    heap.size = 4;
    cout << "Is heap full? "
         << (heap.isFull() ? "true" : "false")
         << endl;
    // Output: false (heap has space)
    return 0;
}

Note: For linked list-based heaps, isFull() is typically not needed as they can grow dynamically until the system runs out of memory. ...

Insert