學習堆排序，首先需要明白堆的概念，堆是一個數組。可以近似當做完全二叉樹的數組存儲方式。但是跟他還有其他的性質，就是類似于二叉排序樹。有最大堆跟最小堆之分，最大堆是指根節點的值都大于子節點的值，而最小堆的是根節點的值小于其子節點的值。堆排序一般用的是最大堆，而最小堆可以構造優先隊列。堆里面有一個方法是用來維護堆的性質，也就是我們下面代碼中的maxheap方法，這是維護最大堆性質的方法，第一個參數就是堆也就是數組，第二個參數是調整堆的具體節點位置，可能這個節點的值不符合最大堆的性質，那么這個值得位置就作為參數，而size其實是堆內實際存儲的有效元素個數?？赡軘到M的長度就是堆內實際存儲的元素個數，但是不一定所有的數據我們都需要進行構建最大堆。算法導論中說的得到左子結點是2xi但是我們數組是從0開始計數的，所以左子結點就成了2xi+1，buildheap就是構建一個最大堆，我們去2分之長度的原因是，這些點的子節點都是葉子節點，所以我們通過從下向上進行排序來構建一個最大堆。保證了我們堆內所有節點都滿足最大堆性質。最后堆排序就是把第一個節點取出來，將剩下的節點再進行堆排序，再取出根節點。這樣保證我們每次取出都是最大值。
public static void main(String[] args) {
int[] heap=new int[]{4,1,5,3,7,12,65,7};
HeapSort hs=new HeapSort();
hs.sort(heap);
for (int i = 0; i < heap.length; i++) {
System.out.println(heap[i]);
}
}
}
新聞熱點
疑難解答
