c++sortingheapsort

How does std::sort_heap break the heap property?


cppreference.com says:

The resulting range no longer has the heap property.

cplusplus.com says:

The range loses its properties as a heap.

What do they mean? It sorts, and sorted implies heap, no?


Solution

  • A list sorted ascending is automatically a min-heap. A list sorted descending is automatically a max-heap. std::sort_heap turns a max heap into a list sorted ascending, which is no longer a max-heap (but it is a min-heap). To reiterate: the subtlety is that the ordering is being reversed. The list is turned from "weakly descending" (max-heap) to ascending (sorted, not a max-heap).