自己實現(xiàn)堆，你能寫出堆排序嗎？

前言

堆這種結(jié)構(gòu)實在是用得太多了，而且一般考到的話都是中等或者困難的題，關(guān)鍵是在沒有提示的情況下，初學(xué)者很難想到可以用堆來進(jìn)行優(yōu)化。

如果對堆還沒概念，我這里簡單描述一下。堆是一種二叉樹，分大頂堆和小頂堆，大頂堆就是根元素要大于左右兩邊的元素，并且左右兩邊都是大頂堆。小頂堆相反，根元素小于左右兩邊的元素，并且左右兩邊都是小頂堆。

所以對于堆來說，堆頂元素是整個堆的最值。堆排序就是利用了堆的這個性質(zhì)，每次將堆頂元素取出，然后剩余元素調(diào)整形成新的堆，再次將堆頂元素取出，這樣最終就能排序了。

外援

首先我們可以用語言自己提供的堆的實現(xiàn)來實現(xiàn)堆排序，看下代碼。

public static void heapSort(int[] arr) {
    PriorityQueue heap = new PriorityQueue<>();
    for(int i = 0; i < arr.length; i++) {
        heap.offer(arr[i]);
    }
    for(int i = 0; i < arr.length; i++) {
        arr[i] = heap.poll();
    }
}

在java中，PriorityQueue就是堆（也叫優(yōu)先隊列），offer方法是把一個元素加入到堆里面，并且內(nèi)部進(jìn)行調(diào)整，使它重新滿足堆的條件，poll方法是將堆頂元素取出，并且內(nèi)部進(jìn)行調(diào)整，使其他元素重新滿足堆的條件。

有了上面的知識我們很簡單就能理解了，我們直接把數(shù)組放到堆里，然后一個個從堆頂取出就好，這樣就自動排好序了。

如果考堆排序，面試官一般不會讓你用PriorityQueue，但是我們也得會，因為如果其他題用到堆，一般是可以直接用PriorityQueue的。

內(nèi)功

自己實現(xiàn)，我們其實就是去實現(xiàn)調(diào)整堆的邏輯。先看一下代碼，我們對著代碼講。

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static void downAdjust(int[] arr, int parent, int end) {
    int left = parent * 2, right = parent * 2 + 1;
    if(left > end) {
        return;
    }
    if(right <= end && arr[parent] < arr[right] && arr[left] < arr[right]) {
        swap(arr, parent, right);
        parent = right;
    } else if(arr[parent] < arr[left]) {
        swap(arr, parent, left);
        parent = left;
    } else {
        return;
    }
    downAdjust(arr, parent, end);
}

public static void heapSort(int[] arr) {
    for(int i = arr.length / 2; i >= 0; i--) {
        downAdjust(arr, i, arr.length - 1);
    }
    for(int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        downAdjust(arr, 0, i - 1);
    }
}

其實主要分兩步，第一步先把原來的數(shù)組變成一個堆，我們從arr.length/2開始，因為再往后都是葉子節(jié)點，沒必要調(diào)整了。而每次調(diào)整，我們調(diào)用的是downAdjust，這個是核心方法。

在downAdjust里面，一定要注意定義一個end作為邊界，然后找到左右孩子，將parent和左右孩子中較大的交換，交換之后將parent設(shè)為孩子的位置，再繼續(xù)遞歸。

這樣全部調(diào)整完之后，就會形成一個大頂堆，然后從后往前，每次把堆頂和數(shù)組元素交換，這樣數(shù)組就變成有序數(shù)組啦。

說實話這個實現(xiàn)還是有一定技巧的，面試中出現(xiàn)的也不多，但是堆這個數(shù)據(jù)結(jié)構(gòu)一定要掌握，面試很有幫助。

練習(xí)題

學(xué)習(xí)完堆排序，大家可以去做一下以下的習(xí)題：

leetcode912?排序數(shù)組

leetcode147?鏈表排序