What Heaps Can Do That Priority Queues Don’t
Heaps are implementations of priority queues. But what’s the point of having multiple STL algorithms that manipulate heaps in the form of a range, if you can directly use a priority queue structure?
What heaps allow you to do that priority queues don’t? This is the question we tackle in this week’s video.
The series on heaps and priority queues contains:
- Part 1: Heaps Basics
- Part 2: Building, Unbuilding and Sorting Heaps (video)
- Part 3: Queues, Priority Queues and Heaps
- Part 4: What Heaps Brings That Priority Queues Don’t (this video)
EDIT: After presenting this topic at the Daily C++ and discussing it with Fred Tingaud, I realized than a more common use case than what follows for using heaps instead of priority queues is to implement Dijkstra’s algorithm to determine the shortest path between two nodes of a graph.
Transcript of the video:
Hello, this is Jonathan Boccara for Fluent C++. This is part 4 in our mixed series of articles and videos about heaps and priority queues in C++.
In part 3, which you can find of the Fluent C++ blog (fluentcpp.com) we left off with the question: why bother with heaps, since priority queues are so much simpler? They just have push and pop and top and that’s it.
Whereas with the heaps there are a lot of algorithms and you can manipulate the whole collection and mess it up and break the heap property. So why bother with heaps, and what can heaps do that priority queues don’t? That what we’re going to talk about today.
The obvious difference is that in a heap you can access the whole collection, whereas in a queue you can only access the largest, the “top” element of the queue. Now what can you do with that whole collection?
Consider the example when you have events coming in with a priority, and you want to process those events according to their priority, and not their order of arrival. For that, you can just use a priority queue.
But now let’s imagine that you have several processors of events at the same time and you want to chunk up the batch of events coming in and send it off to several processors. With a queue you can’t do that. There is no such such thing as a “split” on a priority queue.
But with the heaps, since you have access to the whole structure you can extract a sub-heap (that’s also a heap by construction) and send it off to a processor. And extract a second heap and send that one off to a second processor.
Let’s see how in code we can extract a sub-heap from a heap.
Let’s consider this heap that has 9 as a root:
And let’s extract the sub-tree (which is also a heap) that has 8 as a root.
We’re start by squashing down the heap into an array:
{9, 8, 6, 7, 4, 5, 2, 0, 3, 1}
The purpose is to write a piece of code that extracts a sub-heap starting at index 1, which is the position of 8 here.
int main()
{
std::vector<int> heap = {9, 8, 6, 7, 4, 5, 2, 0, 3, 1};
std::vector<int> subHeap = extractSubHeap(heap, 1);
for (int node : subHeap)
{
std::cout << node << ' ';
}
std::cout << '\n';
}
As we’ve seen in Part 1 of our series, we’ve got the leftChild (resp. rightChild) functions that, given an index, returns the index of the left child (resp. right child) of that index:
size_t leftChild(size_t index)
{
return (index + 1) * 2 - 1;
}
size_t rightChild(size_t index)
{
return (index + 1) * 2;
}
The right way to go about that is to use a queue (not a priority queue, just a queue). It consists in traversing the tree in level-order, which means that we traverse it level by level: the first level, then the level just below, and then the level below it, and so on.
And we keep the indices we visit this way, buliding a collecton of indices that’s in the right order describing the heap. Then we figure out what values correspond to those indices, and push them into the results vector.
Here is the prototype of extractSubHeap:
std::vector<int> extractSubHeap(std::vector<int> const& heap, size_t subRootIndex)
{
We’re going to keep a trace of all the indices corresponding to the sub-heap:
std::vector<size_t> subHeapIndices;
And we’re going to keep a queue of the current indices that we are traversing at a given level:
std::queue<size_t> currentIndices;
Note that I’m using std::queue which is in the header <queue> and that we’ve see in Part 3 of this series on heaps and priority queues.
We’re going to start by pushing the sub-root into the queue:
currentIndices.push(subRootIndex);
and also push the index of the sub-root into the indices of the sub-heap itself.
To do that we go through the queue and push the indices of the children of every index that we meet on the queue. This way we taverse the tree in level order.
while (!currentIndices.empty())
{
size_t index = currentIndices.front();
if (leftChild(index) < heap.size())
{
currentIndices.push(leftChild(index));
subHeapIndices.push_back(leftChild(index));
}
if (rightChild(index) < heap.size())
{
currentIndices.push(rightChild(index));
subHeapIndices.push_back(rightChild(index));
}
currentIndices.pop();
}
Now we retrive the values and push them on the vector to return:
std::vector<int> subHeap;
std::transform(begin(subHeapIndices), end(subHeapIndices), std::back_inserter(subHeap),
[&heap](size_t index){ return heap[index];} );
return subHeap;
In that last part we create a vector to return it, and we take all the indices of the sub-heap, which are in the right order for defining a heap. And we return the values that are in the heap and corresponding to those indices.
Running the program outputs:
8 7 4 0 3 1
This is indeed the desired sub-heap:
We’re going to finish off this algorithm by making it look a little more STL-like, by passing an output iterator and templatize the input range:
template<typename Range, typename OutputIterator>
OutputIterator extractSubHeap(Range const& heap, size_t subRootIndex, OutputIterator out)
{
std::vector<size_t> subHeapIndices;
std::queue<size_t> currentIndices;
currentIndices.push(subRootIndex);
subHeapIndices.push_back(subRootIndex);
while (!currentIndices.empty())
{
size_t index = currentIndices.front();
if (leftChild(index) < heap.size())
{
currentIndices.push(leftChild(index));
subHeapIndices.push_back(leftChild(index));
}
if (rightChild(index) < heap.size())
{
currentIndices.push(rightChild(index));
subHeapIndices.push_back(rightChild(index));
}
currentIndices.pop();
}
std::vector<int> subHeap;
std::transform(begin(subHeapIndices), end(subHeapIndices), out,
[&heap](size_t index){ return heap[index];} );
return out;
}
Now this function is all dressed up as an STL algorithm.
At call site it becomes:
std::vector<int> subHeap; extractSubHeap(heap, 1, std::back_inserter(subHeap));
So that’s one use case where having a heap is useful, as opposed to just having the priority queue. If you know other use cases I’d love to hear about them, you can write about them in the comments section below.
I hope you enjoyed this video and this series about heaps and priority queues. If you want more videos about data structures in C++ or more generally about expressive code in C++ you can just smash up that red button. And if you liked this video, why not put a thumb up, that’d be lovely.
Thank you and I see you next time.
You may also like
Don't want to miss out ? Follow:
Share this post!
