堆排序+代碼實現

堆排序+代碼實現

堆排序

堆,heap,是二叉樹的一種。小根堆有這樣的性質——任意一個結點的值比它的左右孩子都要小。

排序思想

將待排元素看作是完全二叉樹，物理上用一維數組存儲。

實現堆排序需要解決兩個問題：

1.如何將雜亂的完全二叉樹初始化為一個堆？

答：從最後一個非葉結點起，將該節點當做根，自上而下進行調整，使之成為一個堆。然後依次對倒數第二個、倒數第三個、直至正數第一個結點進行此操作。

2.輸出堆頂元素後，如何將余下的元素調整為一個堆？

答：將最後一個結點放在原根結點位置上，以它為根進行上述的調整。

復雜度分析。

二叉樹的層數計算方法，從上往下，1,2,3,4......

耗時的操作有構造初始堆和調整堆兩部分。

對深度為h的堆進行自上而下的調整，最多比較次數為2*(h-1)。

在初始化堆的過程中，完全二叉樹的高度為h，總的比較次數為

綜上，堆排序在復雜度最壞的情況下為O((1)式+(2)式)=O(n*logn)。