C++ : Max Heap / Min Heap Using Priority Queue & Set
Max Heap is, in essence, a tree-based data structure in which the key of the parent node is greater than or equal to the keys of its children.
Similarly, Min Heap is also a tree-based data structure in which the key of the parent node is less than or equal to the keys of its children.
Max Heap and Min Heap could easily be implemented in C++ using priority_queue or set.
Below table offers some comparision.
| Min / Max heap using std :: priority_queue | Min / Max heap using std :: set |
|---|---|
| priority_queue uses a std :: vector as default underlying storage for storing the elements. | set is implemented as a BST ( binary search tree ). Each element of a set is allocated its own memory. |
| - Creates a max heap by default. | - Creates a min heap by default. |
| - Inserting into a heap ( min or max ) created using priority_queue takes O ( log n ) time. [ Inserting into a heap created using a priority_queue could be slightly faster because of the underlying storage. ] | - Inserting into a heap ( min or max ) created using set takes O ( log n ) time. [ Inserting into a heap created using a set could be slightly slower as memory allocations are needed. ] |
| - Accessing the element at the top of the heap ( min or max ) takes O ( 1 ) time using <priority_queue>.top(). | - The biggest element at the top and the smallest element can be accessed in O ( 1 ) time using forward and reverse iterators respectively. |
| - As a priorty_queue does not support find operation, an element in a heap ( min or max ) cannot be searched for. | - Any element of the set can be found in O ( log n ) time. Thus any element of a heap can easily be searched for. |
| - Only the element at the top of the heap created using priority_queue can be removed. Removing the element at the top of heap ( min or max ) takes O ( log n ) time. | - Any element of the heap created using set can be removed. Removing the element in the heap ( min or max ) takes O ( log n ) time. |
Creating a heap using a priority_queue takes O ( n ) time. Removing the element from the top of the heap takes O ( log n ) time.
Thus, the heap sort algorithm takes O ( n log n ) time to run.
Example
#include<iostream>
#include<queue>
#include<vector>
class Mountain {
public:
std :: string name;
int height;
Mountain ( std :: string arg_name, int arg_height) : name(arg_name), height(arg_height)
{}
bool operator < (const Mountain& obj) const {
if (this->name.size() < obj.name.size()) {
return true;
}
return false;
}
};
class CompareName {
public:
bool operator() (const Mountain& a, const Mountain& b) const {
// Mountain with smaller name goes below
if (a.name.size() < b.name.size())
return true;
return false;
}
};
int main() {
//std :: priority_queue<Mountain, std :: vector<Mountain>, CompareName> pq_mountains;
std :: priority_queue<Mountain> pq_mountains;
Mountain m1("K2", 8611);
Mountain m2("Kangchenjunga", 8586);
Mountain m3("Everest", 8848);
Mountain m4("Annapurna", 8091);
pq_mountains.push(m1);
pq_mountains.push(m2);
pq_mountains.push(m3);
pq_mountains.push(m4);
std :: cout << "Max heap using priority_queue." << std :: endl;
std :: cout << "Arranging mountain name(s) based on the length (max_heap) of the names." << std :: endl;
std :: cout << "Mountain with longest name comes at the top.\n" << std :: endl;
while (!pq_mountains.empty()) {
Mountain mount = pq_mountains.top();
pq_mountains.pop();
std :: cout << mount.name << " " << mount.height << std :: endl;
}
std :: vector<int> vec_nums { 5, 2, 7, 13, 11 };
std :: priority_queue<int> pq_maxheap (vec_nums.begin(), vec_nums.end());
std :: cout << "\nElements in vector : ";
for (const auto& num : vec_nums) {
std :: cout << num << " ";
}
std :: cout << "\nElements in max heap (created from vector) : ";
while (!pq_maxheap.empty()) {
std :: cout << pq_maxheap.top() << " ";
pq_maxheap.pop();
}
std :: priority_queue<int, std :: vector<int>, std :: greater<int>> pq_minheap;
pq_minheap.push(5);
pq_minheap.push(2);
pq_minheap.push(7);
pq_minheap.push(13);
pq_minheap.push(11);
std :: cout << "\nElements in min heap (created from vector) : ";
while (!pq_minheap.empty()) {
std :: cout << pq_minheap.top() << " ";
pq_minheap.pop();
}
return 0;
}
Output
Max heap using priority_queue.
Arranging mountain name(s) based on the length (max_heap) of the names.
Mountain with longest name comes at the top.
Kangchenjunga 8586
Annapurna 8091
Everest 8848
K2 8611
Elements in vector : 5 2 7 13 11
Elements in max heap (created from vector) : 13 11 7 5 2
Elements in min heap (created from vector) : 2 5 7 11 13
#include<iostream>
#include<set>
#include<vector>
class Mountain {
public:
std :: string name;
int height;
Mountain ( std :: string arg_name, int arg_height) : name(arg_name), height(arg_height)
{}
bool operator < (const Mountain& obj) const {
if (this->name.size() > obj.name.size()) {
return true;
}
return false;
}
};
class CompareName {
public:
bool operator() (const Mountain& a, const Mountain& b) const {
// Mountain with bigger name goes below
if (a.name.size() > b.name.size())
return true;
return false;
}
};
int main()
{
//std :: set<Mountain, CompareName> set_mountains;
std :: set<Mountain> set_mountains;
Mountain m1("K2", 8611);
Mountain m2("Kangchenjunga", 8586);
Mountain m3("Everest", 8848);
Mountain m4("Annapurna", 8091);
set_mountains.insert(m1);
set_mountains.insert(m2);
set_mountains.insert(m3);
set_mountains.insert(m4);
std :: cout << "Arranging mountain name(s) based on the length (max_heap) of the names." << std :: endl;
std :: cout << "Mountain with longest name comes at the top.\n" << std :: endl;
while (!set_mountains.empty()) {
Mountain mount = *set_mountains.cbegin();
set_mountains.erase(set_mountains.cbegin());
std :: cout << mount.name << " " << mount.height << std :: endl;
}
std :: vector<int> vec_nums { 5, 2, 7, 13, 11 };
std :: cout << "\nElements in vector : ";
for (const auto& num : vec_nums) {
std :: cout << num << " ";
}
std :: set<int, std::greater<int>> set_maxheap (vec_nums.cbegin(), vec_nums.cend());
std :: cout << "\nMax Heap using set." << std :: endl;
std :: cout << "Biggest element (root) : " << *set_maxheap.cbegin() << std :: endl;
std :: cout << "Smallest element : " << *set_maxheap.crbegin() << std :: endl;
std :: cout << "Elements in max heap (created from vector) : ";
while (!set_maxheap.empty()) {
std :: cout << *set_maxheap.cbegin() << " ";
set_maxheap.erase(*set_maxheap.cbegin());
}
std :: set<int> set_minheap;
set_minheap.insert(5);
set_minheap.insert(2);
set_minheap.insert(7);
set_minheap.insert(13);
set_minheap.insert(11);
std :: cout << "\n\nMin Heap using set." << std :: endl;
std :: cout << "Smallest element (root) : " << *set_minheap.cbegin() << std :: endl;
std :: cout << "Biggest element : " << *set_minheap.crbegin() << std :: endl;
std :: cout << "Elements in min heap : ";
while (!set_minheap.empty()) {
std :: cout << *set_minheap.cbegin() << " ";
set_minheap.erase(*set_minheap.cbegin());
}
return 0;
}
Output
Max Heap using set.
Arranging mountain name(s) based on the length (max_heap) of the names.
Mountain with longest name comes at the top.
Kangchenjunga 8586
Annapurna 8091
Everest 8848
K2 8611
Elements in vector : 5 2 7 13 11
Max Heap using set.
Biggest element (root) : 13
Smallest element : 2
Elements in max heap (created from vector) : 13 11 7 5 2
Min Heap using set.
Smallest element (root) : 2
Biggest element : 13
Elements in min heap : 2 5 7 11 13