Now consider if you have a heap like this
now
you can see it is not a max heap due to node with key 4 (i=2).with the
help of simple algorithm we can place this node to the correct position
so that this tree can again satisfy max heap property.
[cpp]
void max_heapify_recursive(int A[],int n,int i){
int left=2*i;
int right=2*i+1;
int largest;
if(left<=n && A[left]>A[i])
largest=left;
else largest =i;
if(right<=n && A[right]>A[largest])
largest=right;
if(largest!=i){
swap(A[largest],A[i]);
max_heapify_recursive(A,n,largest);
}
}
[/cpp]
you can have iterative version also (more efficient on some computers)
[cpp]
void max_heapify_iterative (int A[],int n,int i){
int left,right,largest;
largest=i;
do{
i=largest;
left=2*i;
right=2*i+1;
if (left <=n && A[left]>A[i])
largest=left ;
else largest=i;
if(right<=n && A[right]>A[largest])
largest=right;
if (largest!=i)
swap(A[largest],A[i]);
}while(largest!=i);
}
[/cpp]
for max_heapify
best case will occur when the node with i index is already satisfying the max heap property (eg i=1 or i=2).In this case both the recursive and iterative versions will take omega(1) time
worst case will occur when i=1 and the key of i=1 is minimum in the tree .In this case the algorithm will traverse from root to the child node thus traversing the complete height,
so Time complexity is O(log n)
same as you will use one of above two procedures to max heapify (applying max heap property),you can also have min -heapify to apply min heap property
[cpp]
void min_heapify_recursive(int A[],int i){
int left=2*i;
int right=2*i+1;
int smallest;
if(left<=n && A[left]<A[i])
smallest=left;
else smallest =i;
if(right<=n && A[right]<A[smallest])
smallest=right;
if(smallest!=i){
swap(A[smallest],A[i]);
min_heapify_recursive(A,smallest);
}
}
[/cpp]
you can have iterative version also (more efficient on some computers)
[cpp]
void min_heapify_iterative (int A[],int i){
int left,right,smallest;
smallest=i;
do{
i=smallest;
left=2*i;
right=2*i+1;
if (left <=n && A[left]>A[i])
smallest=left ;
else smallest=i;
if(right<=n && A[right]>A[largest])
smallest=right;
if (smallest!=i)
swap(A[smallest],A[i]);
}while(smallest!=i);
}
[/cpp]
for min_heapify
best case will occur when the node with i index is already satisfying the min heap property (eg i=2 or i=3).In this case both the recursive and iterative versions will take omega(1) time
worst case will occur when i=1 and the key of i=1 is maximum in the tree .In this case the algorithm will traverse from root to the child node thus traversing the complete height,
so Time complexity is O(log n)
time complexity
0 comments: