What is the concrete aim of using max heap for priority queue

Question

Max heap are used for priority queue, because of cheap extraction of max element.

However, please tolerate me.

Shouldn't we just search the max element in O(N) times?

I know that to extract max we require just O(log N) time, but before we can do that we need to build a heap, which itself require O(N) time.

So why do we go through so much complexity of even implementing heap?

Also, some might say that to perform repetitive extract max heaps are an advantage.

But let's say we perform k search operations so by linear search we get O(KN) ==O(N), which is same as heap O(N + K) == O(N)

If we perform N extract max we get O(NLogN) which is better than (NN)==(N^2) search operations.

But there too we could sort an array in O(NlogN) and then have N extracts in O(1) time ==> O(NlogN) + O(N).

So my doubt is that, do we really need heaps? When we can have replace the functionality of heap to much similar procedure if not a better one.

What am I missing out, and for what are heaps really used for.

Forgive my ignorance, and bad usage of grammar. Not a native speaker, sorry :(....

Answer 1

You can use a heap to sort that array in O(n log n)-time in the worst case (unlike Quicksort, unless you implement a complicated pivot selection procedure that's not really practical) and without additional space (unlike Mergesort, unless you implement a complicated in-place merge that is not practical at all).

Heaps really shine when you intermix insertion and extraction though (e.g., Dijkstra's algorithm, Prim's algorithm).

Answer 2

Consider a scenario where you mix N inserts and N extractions.

For a heap you get O(NlogN) total steps.

For a naive approach you get O(N^2) total steps.

For a sort approach (upon insertion add elements at the end, upon query sort) you also get O(N^2) total steps.

Answer 3

Think of how a priority queue is used in the real world. You add some things, take some away, add some more, extract some, etc. With a heap, both Add and Remove are, in the worst case, O(log n). With a list, either Add is O(1) or Remove is O(1). The other is O(n). Typically you would want Add to be O(n) so that the list is always sorted and the Peek operation can be O(1).

So, given a sequence of Add and Remove operations, when there are already 1,000 items in the heap:

Operation     Heap    List
Add           log n     n
Add           log n     n
Remove        log n     1
Add           log n     n
Add           log n     n
Add           log n     n
Remove        log n     1
Remove        log n     1
Remove        log n     1
Remove        log n     1

That's 10*log(n) for the heap, and 5n + 5 for the list. log(n) of 1,000 is about 10. So you're talking on the order of 100 operations for a heap. For the list, you're talking on the order of 5,000 operations. So the heap would be 50 times as fast. If you have a million items in the list, you're talking about 200 operations for a heap, and 5 million operations for a list.

If you just want to go through a bunch of items in-order, then it doesn't really make sense to use a priority queue. A sorted list works just fine, and will likely be faster than building a priority queue and pulling items off one-by-one. (Although you might end up using a heap sort to sort the items in the first place.)

Use the right tool for the job.