Max Heap in C++ - Naukri Code 360

Introduction

A heap is a tree-based data structure where the element with the highest or the lowest priority is always stored at the ‘root’ of the tree. There are two types of heaps: max and min. A max heap is a specialized tree-based data structure in which the parent node is always greater than or equal to its child nodes. This property makes max heaps useful for implementing priority queues and for quickly finding the maximum element in a collection. In C++, max heaps can be efficiently implemented using an array or vector.

In this article, we'll discuss what max heaps are and how they work, as well as see examples of implementing them in C++.

Purpose and Use Cases of Max-Heap

A max heap is a data structure that follows the heap property, which states that the value of each node must be greater than or equal to the values of its children. This property makes Max Heaps very useful in many situations.

One of the primary use cases for max heaps is implementing priority queues. In a priority queue, elements are assigned priorities, & the element with the highest priority is always served first. Max heaps provide an efficient way to implement priority queues because the maximum element (i.e., the element with the highest priority) is always at the root of the heap. This allows for constant-time access to the maximum element.

Another common use case for max heaps is finding the k largest or k smallest elements in a collection. By constructing a max heap from the elements and repeatedly extracting the maximum element k times, we can find the k largest elements in the collection. Similarly, by constructing a min heap (where the minimum element is at the root) and extracting the minimum element k times, we can find the k smallest elements.

Max heaps are also used in some graph algorithms, such as Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm. In these algorithms, max heaps efficiently select the vertex with the maximum value from a set of vertices.

In summary, max heaps are particularly useful when we need to access the maximum element efficiently, find the k largest or smallest elements, or implement priority queues. Their efficient insertion & deletion operations make them a valuable tool in various algorithmic scenarios.

Syntax

In C++, a max heap can be implemented using an array or a vector. The elements are stored in a specific order that satisfies the heap property. For a max heap, the property states that for any given node i, the value of the node is greater than or equal to the values of its children.

The syntax for creating a max heap using a vector in C++ is:

#include <vector>

std::vector<int> maxHeap;

To insert an element into the max heap, we use the `push_back()` function to add the element to the end of the vector and then use the `push_heap()` function from the `<algorithm>` library to restore the heap property:

#include <algorithm>
maxHeap.push_back(element);
std::push_heap(maxHeap.begin(), maxHeap.end());

To remove the maximum element (which is always at the root), we use the `pop_heap()` function to move the root element to the end of the vector and then use the `pop_back()` function to remove it:

std::pop_heap(maxHeap.begin(), maxHeap.end());
maxHeap.pop_back();

The `<algorithm>` library provides several other useful functions for working with heaps, such as `make_heap()` to construct a heap from a range of elements and `sort_heap()` to sort the elements in the heap.

Example

Let's see a complete example of implementing a max heap in C++:

In this example, we'll create a class called `MaxHeap` that encapsulates the max heap functionality.

#include <vector>
#include <algorithm>
class MaxHeap {
private:
    std::vector<int> heap;


public:
    void push(int value) {
        heap.push_back(value);
        std::push_heap(heap.begin(), heap.end());
    }

    void pop() {
        if (!isEmpty()) {
            std::pop_heap(heap.begin(), heap.end());
            heap.pop_back();
        }
    }

    int top() {
        if (!isEmpty()) {
            return heap.front();
        }
        return -1; // or throw an exception
    }


    bool isEmpty() {
        return heap.empty();
    }


    int size() {
        return heap.size();
    }
};

In this example, the `MaxHeap` class has a private member `heap` which is a vector that stores the elements of the heap. The class provides the following public member functions:

`push(int value)`: Inserts an element into the max heap.
`pop()`: Removes the maximum element (root) from the max heap.
`top()`: Returns the maximum element (root) without removing it.
`isEmpty()`: Checks if the max heap is empty.
`size()`: Returns the number of elements in the max heap.

Let’s see an example of how to use the `MaxHeap` class:

#include <iostream>
int main() {
    MaxHeap maxHeap;

    maxHeap.push(10);
    maxHeap.push(30);
    maxHeap.push(20);
    maxHeap.push(40);


    while (!maxHeap.isEmpty()) {
        std::cout << maxHeap.top() << " ";
        maxHeap.pop();
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

40 30 20 10

In this example, we create an instance of the `MaxHeap` class and insert the elements 10, 30, 20, and 40 into the max heap using the `push()` function. Then, we use a while loop to repeatedly remove and print the maximum element from the heap until it becomes empty.

The output shows that the elements are removed in descending order (40, 30, 20, 10), which verifies that the max heap property is satisfied.

How to create a min heap for the priority queue?

To create a min heap for a priority queue in C++, you can use the `std::priority_queue` class from the `<queue>` header. By default, `std::priority_queue` creates a max heap, but you can specify a custom comparator to make it behave as a min heap.

Let’s see how you can create a min heap for a priority queue:

#include <queue>
#include <vector>


// Define a custom comparator for min heap
struct CompareGreater {
    bool operator()(int a, int b) {
        return a > b;
    }
};


// Create a min heap priority queue
std::priority_queue<int, std::vector<int>, CompareGreater> minHeap;

In this code:

We include the necessary headers: `<queue>` for the `std::priority_queue` class and `<vector>` for the underlying container.
We define a custom comparator struct called `CompareGreater` that overloads the `operator()` function. This comparator reverses the default comparison order, making the priority queue behave as a min heap.
We create a `std::priority_queue` named `minHeap` and specify the element type as `int`, the underlying container as `std::vector<int>`, and the comparator as `CompareGreater`.

Now, you can use the `minHeap` object to perform operations on the min heap priority queue, such as inserting elements using `push()`, accessing the minimum element using `top()`, and removing the minimum element using `pop()`.

Let’s discuss an example of how to use the min heap priority queue:

minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
minHeap.push(5);

while (!minHeap.empty()) {
    std::cout << minHeap.top() << " ";
    minHeap.pop();
}

Output:

5 10 20 30

In this example, we push the elements 10, 30, 20, and 5 into the min heap priority queue. Then, we use a while loop to repeatedly remove and print the minimum element from the heap until it becomes empty.

The output shows that the elements are removed in ascending order (5, 10, 20, 30), which verifies that the min heap property is satisfied.

Methods of Priority Queue

The `std::priority_queue` class in C++ provides several methods to perform operations on the priority queue. Here are the commonly used methods:

1. `push(value)`: Inserts an element into the priority queue.

2. `pop()`: Removes the top element (highest priority) from the priority queue.

3. `top()`: Returns the top element (highest priority) without removing it.

4. `empty()`: Checks if the priority queue is empty.

5. `size()`: Returns the number of elements in the priority queue.

For example:

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    std::cout << "Size: " << pq.size() << std::endl;
    std::cout << "Top element: " << pq.top() << std::endl;

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Size: 4
Top element: 50
50 30 20 10

In this example:

We create a `std::priority_queue` object named `pq`.
We insert elements into the priority queue using the `push()` method.
We print the size of the priority queue using the `size()` method.
We access the top element (highest priority) using the `top()` method and print it.
We use a while loop to remove and print the elements from the priority queue until it becomes empty, using the `top()` and `pop()` methods.

The output shows the size of the priority queue, the top element, and the elements removed in descending order of priority.

Operations on Priority Queue in C++

Priority queues in C++ support various operations that allow you to manipulate the elements based on their priorities. Here are the common operations performed on priority queues:

1. Insertion

Elements can be inserted into the priority queue using the `push()` method.
The inserted element is automatically placed in the correct position based on its priority.
The time complexity of insertion is O(log n), where n is the number of elements in the priority queue.

Example:

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

50 30 20 10

2. Deletion

The top element (highest priority) can be removed from the priority queue using the `pop()` method.
The time complexity of deletion is O(log n), as the priority queue needs to be restructured after removing the top element.

Example:

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    std::cout << "Top element before deletion: " << pq.top() << std::endl;

    pq.pop();

    std::cout << "Top element after deletion: " << pq.top() << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Top element before deletion: 50
Top element after deletion: 30

3. Accessing the top element:

The top element (highest priority) can be accessed using the `top()` method.
This operation has a time complexity of O(1), as the top element is always readily available.

Example:

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    std::cout << "Top element: " << pq.top() << std::endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Top element: 50

4. Checking if the priority queue is empty

You can check if the priority queue is empty using the `empty()` method.
This operation has a time complexity of O(1).

Example:

#include <iostream>
#include <queue>


int main() {
    std::priority_queue<int> pq;
    if (pq.empty()) {
        std::cout << "Priority queue is empty." << std::endl;
    } else {
        std::cout << "Priority queue is not empty." << std::endl;
    }

    pq.push(10);

    if (pq.empty()) {
        std::cout << "Priority queue is empty." << std::endl;
    } else {
        std::cout << "Priority queue is not empty." << std::endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Priority queue is empty.
Priority queue is not empty.

5. Getting the size of the priority queue:

The number of elements in the priority queue can be obtained using the `size()` method.
This operation has a time complexity of O(1).

Example:

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    std::cout << "Size: " << pq.size() << std::endl;

    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    std::cout << "Size: " << pq.size() << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Size: 0
Size: 4

Complexities Of All The Operations

1. Insertion (push)

Time Complexity: O(log n), where n is the number of elements in the priority queue.
Explanation: When an element is inserted, it is added to the end of the underlying container (e.g., vector or array) and then the heap property is restored by comparing and swapping elements with their parent nodes. This process takes logarithmic time in the worst case.

2. Deletion (pop)

Time Complexity: O(log n), where n is the number of elements in the priority queue.
Explanation: When the top element (highest priority) is removed, it is replaced by the last element in the underlying container. Then, the heap property is restored by comparing and swapping elements with their child nodes until the heap property is satisfied. This process takes logarithmic time in the worst case.

3. Accessing the top element (top)

Time Complexity: O(1).
Explanation: Accessing the top element (highest priority) is a constant time operation because the top element is always stored at the root of the heap.

4. Checking if the priority queue is empty (empty)

Time Complexity: O(1).
Explanation: Checking if the priority queue is empty is a constant time operation. It typically involves comparing the size of the priority queue with zero.

5. Getting the size of the priority queue (size)

Time Complexity: O(1).
Explanation: Getting the size of the priority queue is a constant time operation. The size is usually stored as a separate variable and updated whenever elements are inserted or deleted.

Space Complexity

The space complexity of a priority queue is O(n), where n is the number of elements stored in the priority queue.
This is because the priority queue uses an underlying container (e.g., vector or array) to store the elements, and the space required grows linearly with the number of elements.

Frequently Asked Questions

Can a priority queue contain elements with the same priority?

Yes, a priority queue can store elements with the same priority. In such cases, the elements with the same priority are typically processed in the order they were inserted.

Is it possible to change the priority of an element already in the priority queue?

No, once an element is inserted into the priority queue, its priority cannot be directly changed. If you need to change the priority, you would have to remove the element and reinsert it with the new priority.

Can a priority queue be used to sort elements in ascending order?

Yes, a priority queue can be used as a sorting mechanism. By inserting all the elements into a priority queue and then removing them one by one, you will obtain the elements in sorted order based on their priorities.

Conclusion

In this article, we discussed the concept of max heap & its implementation in C++. We learned about the purpose & use cases of max heaps, their syntax, & how to create them using arrays or vectors. We also looked into the methods and operations that are supported by priority queues, along with their time & space complexities. Max heaps is a very valuable data structure for efficient access to the maximum element and when priority-based operations are required.

You can also check out our other blogs on Code360.