STL Heap

[daviddoria]

I just learned about heaps today. It looks like STL wants you to create a heap by first creating a vector, then using make_heap from <algorithm>:

std::vector<SimpleClass> Numbers(8);
// ... populate ...

  // convert Numbers into a heap
  make_heap(Numbers.begin(), Numbers.end()) ;

Why is there not a <heap> just as is there is a <set>, etc?

Thanks,

David

[Narue]

>Why is there not a <heap> just as is there is a <set>, etc?
<priority_queue>, perhaps?

[daviddoria]

I see... why do they provide these make_heap functions then?

[Narue]

I could speculate, but not being privy to the thought process of the designer makes answering your question difficult.

[gashtio]

I see... why do they provide these make_heap functions then?

Because you might have an existing collection that you want to turn into a heap in-place, instead of duplicating the elements using push es into a priority_queue .

Or, if you want to guarantee a O(nlogn) bound of a sort, you can use make_heap alongside sort_heap to produce heap sort (although library implementations of std::sort usually have optimizations so it doesn't degenerate to O(n^2)).

[mrnutty]

>>although library implementations of std::sort usually have optimizations so it doesn't degenerate to O(n^2)).

Does that mean the stl guarantee that they use quicksort for std::sort?

[Narue]

>Does that mean the stl guarantee that they use quicksort for std::sort?
No, though you'll find that introsort (a variation of quicksort) is the preferred implementation.