CODEWITHSUNDEEP
c++sortingc++11
Ivaylo Valchev
Ivaylo Valchev

Reputation: 10425

std::sort_heap in descending order

So I came across this code. The only thing I added was the predicate parameter.

template<class RandomAccessIt, class Predicate = std::less<>> inline
void heap_sort(RandomAccessIt first, RandomAccessIt last, Predicate predicate = Predicate())
{
    std::make_heap(first, last);
    std::sort_heap(first, last, predicate);
}

Now as the title says, it works fine with:

int arr[] = { 143, 2, 365, 4, 5 };
heap_sort(std::begin(arr), std::end(arr));

But gives me a debug error (invalid heap) with:

int arr[] = { 143, 2, 365, 4, 5 };
heap_sort(std::begin(arr), std::end(arr), std::greater<>());

I also tried this with other containers. What is the point of allowing a custom UnaryPredicate then?

Upvotes: 2

Views: 563

Answers (1)

Baum mit Augen
Baum mit Augen

Reputation: 50111

std::make_heap

needs to be called with the same predicate:

std::make_heap(first, last, predicate);
std::sort_heap(first, last, predicate);

Otherwise, the heap is built with the wrong criterion and will not be a max heap with respect to predicate. This violates the precondition for std::sort_heap(first, last, predicate);.

Upvotes: 2

Related Questions