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

explaining Heap property heapsort 1) 

Here are Some Basics of Heap 

More in Heapsort part 2)

Efforts summed up as a PDF :) CLICK HERE

just did the shunting yard algorithm's implementation in solving the question on spoj and codechef 'Transform the Expression' done finally after many days of pondering and the SRM and Codeforces round didn't go according to plan so feeling a bit sorry but anyways life moves on :) here is an implementation of the algorithm:- ONP solution link  trivial implementation using STL.  

After the sad demise of Harsha Suryanarayana aka humblefool (the highest rated topcoder from India) Topcoder community has decided to dedicate the single round match 625 to him , what a remarkable community we coders make , we maybe labelled as whatever (nerds , antisocial geeks) but in times like this (the tragic loss of a member of community ) we all stand united , moreover all the winners have an option to donate their prize money to Harsha sir's wife and to my prediction almost everyone would do it . Just looking forward to the match hoping to become green :) may the force be with me :D ............RIP-- humblefool .....................  

The June long challenge ended today been able to solve 4 questions the fourth one digjumps just being a modification of B.F.S. algorithm special thanks to my freind Ansh Khanna for motivating me to do the 4th problem and update this blog :) Ansh if you are reading this a big thanks man . Now talking about the readability of the problem it was not very good i thought i-1(Si-1) meant the the difference of the index and the value of the sequence at i-1 index. So now thinking of framing a similar question for codechef :P not in near future though :) anyways here is the problem link
 QUESTION 4 JUNELONG DIGITJUMPS
my solution
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <queue>
#include <climits>
 
using namespace std;
#define FOR(i,a) for(int i = 0;i < a;i++)
#define REP(i,a,b) for(int i = a;i < b;i++)
#define vi vector<int>
 
int main()
{
int arr[100001],len;/*the dp matrix storing the min moves taken to reach the element and the length of input string*/
char str[100001];/*the string*/
int allnum[10][100001];/*all the numbers position stored from 0-9*/
int allcnt[10];/*counts of all the numbers*/
bool truth[10];/*checks whethers the numbers encountered before or not*/
memset(arr,-1,100001*sizeof(int));/*intitialisation of the dp matrix*/
memset(str,'\0',100001*sizeof(char));/*sting init*/
memset(allcnt,0,10*sizeof(int));/*zero elements initially*/
memset(truth,false,10*sizeof(bool));
std::queue<int> q;/*the queue for storing positions*/
scanf("%s",str);
len=strlen(str);
for(int i=0;i<len;i++)
{
allnum[str[i]-'0'][allcnt[str[i]-'0']]=i;/*storing in the 2D array allnum the positions of numbers*/
allcnt[str[i]-'0']++;/*increase the size*/
}
arr[0]=0;/*no moves required to reach the index 0*/
q.push(0);/*beginning insert the zero*/
while(!q.empty())
{
if(!truth[str[q.front()]-'0'])/*if all the elements of the front type are not pushed*/
{
for(int i=0;i<allcnt[str[q.front()]-'0'];i++)/*i< allcount or total size of the particular element of the front type*/
{if(allnum[str[q.front()]-'0'][i]!=0)
q.push(allnum[str[q.front()]-'0'][i]);/*push the positions of elements in the queue*/

if(arr[q.front()]+1 < arr[allnum[str[q.front()]-'0'][i]] &&arr[allnum[str[q.front()]-'0'][i]]!=-1 )
{
arr[allnum[str[q.front()]-'0'][i]]=arr[q.front()]+1;/*transferring to the dp arr the lowest possible reach*/
}
if(arr[allnum[str[q.front()]-'0'][i]]==-1)
{
arr[allnum[str[q.front()]-'0'][i]]=arr[q.front()]+1;
}

}
truth[str[q.front()]-'0']=true;/*not repeating it next time*/
}
if(q.front()-1>=0)
{
if(arr[q.front()-1]>arr[q.front()]+1&&arr[q.front()-1]!=-1)
{
arr[q.front()-1]=arr[q.front()]+1;
q.push(q.front()-1);
}
if(arr[q.front()-1]==-1)
{
arr[q.front()-1]=arr[q.front()]+1;
q.push(q.front()-1);
}
}

if (q.front()+1<len)
{
if(arr[q.front()+1]>arr[q.front()]+1&&arr[q.front()+1]!=-1)
{
arr[q.front()+1]=arr[q.front()]+1;
q.push(q.front()+1);
}
if(arr[q.front()+1]==-1)
{
arr[q.front()+1]=arr[q.front()]+1;0
q.push(q.front()+1);
}
}
q.pop();
}
printf("%d\n",arr[len-1]);
return 0;
}
by the way it got AC in one go with a runtime of 0.00s memory of 7MB B-) but i have also seen far easier approaches from other people's code and editorials will try to learn them up as well and if possible write them here.