Heapsort part 2 (please check the link of pdf of heapsort 1 before reading this )
So if we
know what a binary heap is and what are its properties we will go to a standard
procedure(read function) called heapify ,to maintain heap property at a
particular index i.
For example
if we consider our heap doesn't follow heap property at a particular index like:-
A call to heapify
at index 2 will convert the array into :-
Finally the
last call will make sure that 10 takes up the correct place:-
It may be a
bit of intuition for some of experienced persons to catch the recursive element
involved in the heapify method but for all the others there is iteration . Yes
, good old iteration can do sufficiently as much as recursion in this case of
heapify.
pseudo code :
heapify (A,i)
l=2i # we can also do l=left_child(i)
r=2i+1 # we can also do r=right_child(i)
if l<heap_size(A) and A[l]
>A[i]
large=l
else
large=r
if r<heap_size(A) and A[r]>A[large]
large=r
if large != i
exchange (A[i],A[large])
heapify(A,largest)
In code //
C++
recursive
heapify
1.void heapify(int A[1000000],int i,int n)
2.{
3. int l=2*i+1;
4. int r=2*i+2;
5. int largest;
6. if(l<n&&A[l]>A[i])
7. {
8. largest=l;
9. }
10.
else
11.
{
12.
largest=i;
13.
}
14.
if(r<n&&A[r]>A[largest])
15.
{
16.
largest=r;
17.
}
18.
if(largest!=i)
19.
{
20.
int temp=A[i];
21.
A[i]=A[largest];
22.
A[largest]=temp;
23.
heapify(A,largest,n);
24.
}
25.
}
Iterative heapify :-
1. void itheapify(int A[100],int i,int n)
2.{
3.int flag=1;
4.int t=i;
5.while(flag==1)
6.{
7. flag=0;
8. int l=2*t+1;
9. int r=2*t+2;
10.
int largest;
11.
if(l<n&&A[l]>A[i])
12.
{
13.
largest=l;
14.
}
15.
else
16.
{
17.
largest=t;
18.
}
19.
if(r<n&&A[r]>A[largest])
20.
{
21.
largest=r;
22.
}
23.
if(largest!=t)
24.
{
25.
int temp=A[t];
26.
A[t]=A[largest];
27.
A[largest]=temp;
28.
t=largest;
29.
flag=1;
30.
}
31.
}
32.
}
In Python
1.def heapify (A,i,n):
2. l=2*i+1
3. r=2*i+2
4. if l<n and A[l]>A[i]:
5. largest = l
6. else:
7. largest = i
8. if r<n and A[r]>A[largest]:
9. largest = r
10.
if largest != i:
11.
A[i],A[largest]=A[largest],A[i]
12.
heapify (A,largest,n)
Running Time
of heapify:-
It is
denoted by a complicated recurrence
T(n) <=
T(2n/3) + O(1)
On solving
by master theoram it comes to our understanding that running time of heapify is
O(log(n))
BUT AS USUAL
WE WILL NOT GET INTO THAT
By going
with our mere intuition the max number of swaps which need to be performed by
heapify will be log(n)
how exactly
??
assume we
have the least element at the top so the max number of swaps to be performed
will be equal to the height of tree which is log(n) , hence at max heapify will
perform log(n) swaps. So the time complexity of heapify will be O(log(n)) :)
//hence proved by intuition
in
heapsort 3
how to build heap using heapify
how to perform heapsort
Codechef,Spoj problem Tsort done
without using library's sorting function
Running time of heapsort and it's
speciality
Sources :- CLRS01
If you want a Pdf of this post click here
