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 :(....
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).