What is the use of max-heap and min-heap?


What is use of heaps as a data structure?


Heaps more precisely binary heaps are common way of implementing priority queues.
a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it.

The basic usage of max-heap we have seen in heap sort algorithm which can be implemented by min heap too.
Now if you recall doing sorting using heap,the basic thing we do is finding largest element of whole array then move it to the end,then since the last element is at its correct place,now we need to find the maximum of left n-1 elements,we once again do this and than we move the element to the n-1 position.So this way the sorting process happens.
The priority thing is here is the elements value,we want to pick element based on its value at each iteration,i.e the one with highest value.

Now if you will use brute force algorithm here,it will take 0(n) i.e scanning all elements in first iteration to find the largest element and then move it to the last position,then you need to scan n-1 elements again to find the maximum from 1 to n-1 position of array,you can do small optimizations in this approach like you can find first and second largest in one iteration using two variables,then you will can cover all the elements in n/2 iterations but when n is large its still 0(n).

Now how using binary heap helps here,since everytime we know we have to find maximum.We can apply some logic so that we dont have to scan all elements for finding maximum during each iteration.
What we do is prepare max heap,which takes O(n) time when we initially build it,but after that since we have stored the number in the form max heap ,we only have to scan 0(log n) elements to find the maximum again .So we have a algorithm which takes 0(logn) instead of native 0(n) algorithm.

The basic logic is that since we know everytime we will need elements based on same criteria we arrange the elements initially in some way(a max heap here) so that further operations will take only 0(logn) time.

The insertion and deletion in a heap are 0(log n ).
Like in sorting after finding the largest element in first iteration using max heap,it is swapped with last element,now this last element is the new element and needs to be inserted according to heap property,so 0(logn) time.


They are data structures that help us in quick access to the largest(in case of max-heap) or the smallest(in case of min heap), because that element will always be the first element, root element.