堆排序
2018-10-21 本文已影响0人
wncbbnk
PARENT(i)
--return (i-1)/2
LEFT(i)
--return i*2+1
RIGHT(i)
--return i*2+2
MAX_HEAPIFY(A, i)
--l=LEFT(i)
--r=RIGHT(i)
--if l<=A.heapSize and A[l]>A[i]
----largest=l
--else
----largest=i
--if r<=A.heapSize and A[r]>A[largest]
----largest=r
--if largest!=i
----exchange A[i] with A[largest]
----MAX_HEAPIFY(A, largest)
BUILD_MAX_HEAP(A)
--A.heapSize=A.length
--for i =A.heapSize/2-1 down to 0
----MAX_HEAPIFY(A, i)
HEAPSORT(A
--BUILD_MAX_HEAP(A)
--for i=A.length-1 down to 1
----exchange A[0] with A[i]
----A.heapSize=A.heapSize-1
----MAX_HEAPIFY(A, 0)
