Why heaps instead of a sorted container

Question

I'm studying the c++ stl algorithms and am trying to understand the heap ones (make_heap, sort_heap, push_heap, etc). I understand the binary tree it creates and how this would be useful for finding the highest priority item at any given time efficiently. It's not clear to me though how this would be better than maintaining a sorted container in which the highest valued item could simply be popped off the top.

Here's the comparisons, as I see it:

For heaps:

Create the heap: make_heap: O(nlogn) ...wrong! O(n)
Insertion: push_heap: O(logn)
Remove highest: pop_heap: O(logn)
Get sorted list: sort_heap: O(nlogn)

For a sorted container:

Initial sort: sort() O(nlogn)
Insertion: ? O(logn)
Remove highest: pop constant
Get sorted list: already sorted constant

Insertion would require finding the element with the same value or the two elements on either side of the value. In a sorted list this should be O(logn). I don't know a particular algorithm that would do this yet.

In any case, what am I missing? It seems from my analysis above that just maintaining a sorted container is no worse in all cases and better in some.

Thanks!

Edit:

I want to point this out so no one reads this and becomes confused by my question. As rici pointed out, I was mistaken about the complexity of make_heap. I initially thought it was O(n log n), but instead it's O(n). That difference, for me, explains why make_heap would be better than simply maintaining a sorted list.

By "sorted container", do you mean something like a std::vector that has been sorted? Because then insertion is O(n). Or do you mean a container like std::set that internally maintains order by using a tree structure in the background? — j_random_hacker

rici rici · Accepted Answer · 2013-10-31T04:50:28

make_heap is O(n), not O(n log n). For large datasets, it can be quite a lot faster than sorting.

The O(log n) operations (push and remove_min) are probably only a little faster than a balanced binary tree implementation, but their storage overhead is a lot lower, which also improves their cache friendliness. For small objects, like integers, a heap uses around a quarter of the memory that a std::set uses.

Why heaps instead of a sorted container

3 Answers