A heap is a specialized tree-based data structure that satisfies the heap property - the value of each node is greater than or equal to (or less than or equal to) the values of its children.
There are two common types of heaps:
Heaps are typically implemented using arrays, where:
Heaps are useful for implementing priority queues, as they allow efficient retrieval and removal of the maximum/minimum element.
C++ provides several heap functions in the <algorithm> header:
make_heap - Creates a heap from an arraypush_heap - Adds an element to a heap pop_heap - Removes the largest/smallest element from a heap#include <algorithm>
// Create a max heap
std::vector<int> vec = {3, 1, 4, 1, 5, 9};
std::make_heap(vec.begin(), vec.end());
// Add element
vec.push_back(2);
std::push_heap(vec.begin(), vec.end());
// Remove largest element
std::pop_heap(vec.begin(), vec.end());
vec.pop_back();
The heap functions allow manipulating a heap stored in a vector or array efficiently.
A priority queue is an abstract data type that provides 3 main operations:
GetMax/GetMin - Retrieve the maximum/minimum elementExtractMax/ExtractMin - Remove and return the maximum/minimum elementPriority queues maintain elements in order of priority. They are commonly implemented using heaps, as heaps provide efficient O(log n) operations for insertion and extraction of max/min.
In C++, std::priority_queue provides a priority queue implementation using heaps.
#include <queue>
std::priority_queue<int> pq;
// Insert elements
pq.push(3);
pq.push(1);
pq.push(5);
// Get min element
int min = pq.top();
// Remove min element
pq.pop();
std::priority_queue in C++ provides a priority queue implementation using heaps.So heaps give lower level control, while priority queues provide a convenient abstraction. Priority queues are usually preferred unless direct manipulation of a heap is required.
The time complexities of heap operations and priority queue operations are the same - O(log n) for insertion and extraction.
Overall, priority queues provide a more flexible and user-friendly interface for ordered element access. But heaps allow direct manipulation when the raw structure is needed.