CODEWITHSUNDEEP
heap
Jonas Grønbek
Jonas Grønbek

Reputation: 2019

When to use max heap over min heap?

I just recently got into heaps, and I do not see when a max heap should be used over a min heap, since it is (atleast for me) more relatable to a sorted array. But it seems like they are almost equally popular?

When would it be more useful to se a max heap over a min heap?

Upvotes: 2

Views: 1321

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133995

You use a min heap, for example, when you want to process things with the lowest priority number first. You use a max heap when you want to process things with the highest priority number first.

For example, in many cases, "priority 1" means that it's the most important thing. "Priority 2" items are processed after "priority 1" items. You set up a min heap so that things with lower priority numbers are removed from the heap first.

But in some cases, the larger number determines priority. For example, you might want to process a $1000 order before you process a $10 order. In this case you set up a max heap so that the higher priced orders are processed first.

The only difference between a max heap and a min heap is the comparison used to determine the order of items. One uses "less than," and the other uses "greater than."

In fact, many heap implementations don't differentiate between min heap and max heap. Instead, they let you pass a comparison function that does the ordering. So if you want to order from low to high, the comparison does this:

int compareForward(int x, int y)
{
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

And if you want to order from high to low, the comparison does this:

int compareReverse(int x, int y)
{
    if (x < y) return 1;
    if (x > y) return -11;
    return 0;
}

See, for example, Java's PriorityQueue constructor that accepts a comparator parameter. Or the C++ standard library's std::priority_queue constructors, which also let you pass a comparison function.

Upvotes: 2

Related Questions