StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy heaps instead of a sorted container
text
Body
copied!<p>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.</p> <p>Here's the comparisons, as I see it:</p> <p>For heaps:</p> <ul> <li>Create the heap: make_heap: <strong>O(nlogn)</strong> <strong>...wrong! O(n)</strong></li> <li>Insertion: push_heap: <strong>O(logn)</strong></li> <li>Remove highest: pop_heap: <strong>O(logn)</strong> </li> <li>Get sorted list: sort_heap: <strong>O(nlogn)</strong></li> </ul> <p>For a sorted container:</p> <ul> <li>Initial sort: sort() <strong>O(nlogn)</strong></li> <li>Insertion: ? <strong>O(logn)</strong></li> <li>Remove highest: pop <strong>constant</strong></li> <li>Get sorted list: already sorted <strong>constant</strong></li> </ul> <p>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.</p> <p>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.</p> <p>Thanks!</p> <hr> <p>Edit:</p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload