二叉堆

二叉堆是一個數組，它可以被看成一個近似的完全二叉樹。

樹的根節點是A[1]，這樣給定一個節點的下標i，我們可以很容易得到它的父節點、左孩子、右孩子的下標：

Parent(i) return i/2Left(i) return 2iRight(i) return 2i+1

定義最大堆為：A[Parent(i)]A[i]

維護堆的性質Max-Heapify：

Max-Heapify(A,i)l = _Left(i)r = _Right(i)if l <= A.heap-size and A[l]> A[i] largest = lelse largest = iif r<= A.heap-size and A[r]> A[largest] largest = rif largest != i exchange A[i] with A[largest] Max-Heapify(A,largest)

我們可以用自底向上的方法利用過程Max-Heapify把一個大小為n=A.length的數組A[1..n]轉換成最大堆。子數組A(n/2+1..n)中的元素都是樹的葉子節點。

Build-Max-Heap(A)A.heap-size = A.lengthfor i= A.length/2 downto 1 Max-Heapify(A,i)

堆排序

Heap_Sort(A)Build-Max-Heap(A)for i = A.length downto 2 exchange A[1] with A[i] A.heap-size = A.heap-size -1 Max-Heapify(A,1)

推薦閱讀：