概述

介紹堆排序之前, 要先介紹什麼是堆以及最大堆最小堆

什麼是堆

這裡的堆指的不是堆棧中的堆, 而是一種數據結構.

堆可以視為一棵完全的二叉樹,完全二叉樹的一個"優秀"的性質是,除了最底層之外,每一層都是滿的,這使得堆可以利用數組來表示,每一個結點對應數組中的一個元素, 如下所示:

最大堆

最大堆就是堆中每個父節點的元素值都大於等於其孩子結點（如果存在）,這樣的堆就是一個最大堆

顯而易見, 最大堆中的最大元素值出現在根結點(堆頂)

最小堆

最小堆就是堆中每個父節點的元素值都小於等於其孩子結點（如果存在）,這樣的堆就是一個最小堆

因此,最小堆中的最小元素值出現在根結點(堆頂)

數組的索引與節點的關係

parent(i) = (i-1)/2 向下取整
left(i) = 2i+1
rigth(i) = 2i+2

堆排序的思路

將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然後將剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反覆執行，便能得到一個有序序列了

堆排序的時間空間複雜度如下:

Java代碼實現

代碼如下, 就是上邊思路的實現.註釋已經很詳細了.

閱讀更多 學習編程 的文章

關鍵字: 數據結構 技術 二叉樹