C heapスタック並べ替えの実現

3025 ワード

        ,           。         2         :
    
        a[n]
        (1)         a[r]          
        (2)                

        Parent(i):
                return a[(i]
        Left(i):
                return a[(i+1)<<1-1]
        Right(i):
                return a[(i+1)<<1]
   
          (        ):
        a       asize
                      psize
        adjustheap(a,i):
            left = (i+1)<<1-1;
            right = (i+1)<<1;
            big = i
            if left< psize && a[left] >= a[i]
                big =left 
            if right < psize && a[right] >= a[i]
                big = right
            if big != i
                swap(a[big],a[i]
                adjustheap(a,big)
       :
          build(a):
            psize = asize
            for i= psize>>2-1 downto 1
                    adjustheap(a,i)
        :
         sort(a):
           bulid(a)
           psize = size -1
           for i = psize and i>0 and i--:
                 swap(a[i],a[0])
                 psize--;
                 adjustheap(a[i],0)