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)