Building, Unbuilding and Sorting Heaps in C++ with the STL

Now that you’re familiar with what heaps are and how they work, let’s see how the STL lets us manipulate them in C++.

This is Part 2 in our series about heaps and priority queues:

• 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 (video)

Transcript of the video:

Hey, this is Jonathan Boccara for Fluent C++. This is part 2 of our mixed series of videos and articles about heaps and priority queues. If you want to catch up on part 1 you can find it on Fluent C++, the blog.

In this video we’re going to be building heaps, unbuilding heaps and sorting heaps with the STL in C++.

Let’s take the example of a heap:

This is a max heap, the largest element is a the top. We’re going to insert an element. This is quite independent from C++, it’s how to insert an element in the heap data structure.

std::push_heap

We’re going to add 8.8 at the end of the heap. That’s not its right position, so we’re going to make it bubble up its way through the heap. We compare it with its parent and, whenever it’s larger than its parent we swap them together:

This way it will eventually reach its final position.

In C++, heaps are represented as contiguous structures, in std::vectors for example. So we squash down this heap into an array like we saw in Part 1 of the series.

Now to add an element, we’re going to push_back the element at the end of the vector, and call std::push_heap, to make this last element bubble up its way to its final position in the heap:

std::vector myHeap = // ... see Part 1 about std::make_heap
myHeap.push_back(8.8);
std::push_heap(begin(myHeap), end(myHeap));

std::pop_heap

Now how do we remove an element from the heap?

We can only remove one element, the top element. To do that, we’re going to use std::pop_heap. It starts by swapping out the first element, that we want to get rid of, with the last element which is one of the smallest ones.

And then it’s going to make that small element, which is probably not at its right position at the top, bubble its way down the heap to its final position, by comparing to its children. Every time it’s smaller than one of its children, we’re going to swap it out with its maximum child, to make sure that we keep the heap property.

And to actually get rid of the element that used to be at the top of the heap and that is now at the last position in the vector, we do a pop_back on the vector:

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

std::sort_heap

Now if you think about it, if you do that std::pop_heap repeatedly but without popping back the elements from the vector, then the top elements are going to pile up at the end of the vector, in sorted order.

Doing this as many times are as there are elements in the heap ends up with a sorted vector and no more heap.

This is essentially what std::sort_heap does:

std::sort_heap(begin(myHeap), end(myHeap));

It takes a heap and sorts it, and its complexity is maximum 2*N*log(N).

So this is about it for manipulating heaps with the STL. We’ve seen how to build heaps with std::push_heap, how to unbuild heaps with std::pop_heap and how to sort heaps with std::sort_heap.

I hope you’re enjoying this mixed series of articles and videos about heaps and priority queues in C++. If you want more videos about data structures in C++ or more generally expressive code in C++ you can hit that red button just below, subscribe to the Fluent C++ channel. And if you liked this video, why not put a thumb up on it, I’d very much appreciate it!

And I see you for Part 3 on the Fluent C++ blog, fluentcpp.com, to explore queues and priority queues.

Thank you, and I see you next time.

Don't want to miss out ? Follow:   
Share this post!