Min priority queues

now since we have equipped ourselves with the knowledge of heaps,we can use it for some practical purposes.
The most important use of heaps is to sort an array.
how we will do that?
lets look step wise step
suppose you have an array (starting with index 1) like this
A[]={,5,13,2,25,7,17,20,8,4};
lets make a simple complete binary tree with the above array
now we will apply build_max_heap (build_min_heap if we want to sort in descending order) procedure to come up with max heap similar to that in below given image
now you can all see that we have maximum element at the top position or at first position in an array.we will swap A[1] with A[max_size]
decrease the size of array with 1
apply max_heapify on remaining heap and i = 1
you will get this structure
as you can see you again have the mximum element at A[1].swap this with A[size-1] ,decrease the size of heap by 1 and apply max_heapify on i=1 and remaining heap.continue in this way and you will have a sorted array.
c code to implement heap sort
[cpp]
void heap_sort(int A[]){
build_max_heap(A);
for(i=size;i=>2;--i){
swap(A[1],A[i]);
max_heapify(A,i-1,1);
}
time complexity
best case =O(n) {example 5 1 2 3 4}
worst case =O(nlogn)
}
[/cpp]

SHARE THIS