總目錄：地址如下看總綱

http://www.itdecent.cn/p/929ca9e209e8

1、堆的基本介紹

1. 堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。
2. 堆是具有以下性質(zhì)的完全二叉樹：
   1、每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大頂堆。
   2、每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆
   3、注意 : 沒有要求結(jié)點的左孩子的值和右孩子的值的大小關(guān)系。

1、何為大頂堆和小頂堆

1. 大頂堆(升序)
   大頂堆特點：arr[i] >= arr[2*i+1] && arr[i] >= arr[2 * i + 2 ] // i 對應(yīng)第幾個節(jié)點，i從0開始編號

   
   
   image.png
   
   

   我們對堆中的結(jié)點按層進行編號，映射到數(shù)組中就是下面這個樣子:

   
   
   image.png

2. 小頂堆(降序)
   小頂堆特點：arr[i] <= arr[2*i+1] && arr[i] <= arr[2 * i+2] // i 對應(yīng)第幾個節(jié)點，i從0開始編號

   
   
   image.png
3. 一般升序采用大頂堆，降序采用小頂堆

3、堆排序的基本思想

1. 將待排序序列構(gòu)造成一個大頂堆
2. 構(gòu)造完后的整個序列的最大值就是堆頂?shù)母?jié)點
3. 將其與末尾元素進行交換，此時末尾就為最大值
4. 然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便能得到一個有序序列了
5. 可以看到在構(gòu)建大頂堆的過程中，元素的個數(shù)逐漸減少，最后就得到一個有序序列了
6. 大頂堆和小頂堆的代碼本質(zhì)區(qū)別的公式 ：這邊案例寫的是大頂堆(升序)
   大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
   小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

4、詳細案例分解：

1. 步驟一 構(gòu)造初始堆。將給定無序序列構(gòu)造成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)
   （1）假設(shè)給定無序序列結(jié)構(gòu)如下：

   
   
   image.png
   
   

   （2）此時我們從最后一個非葉子結(jié)點開始（葉結(jié)點自然不用調(diào)整，第一個非葉子結(jié)點 arr.length/2-1=5/2-1=1，也就是下面的6結(jié)點），從左至右，從下至上進行調(diào)整

   
   
   image.png
   
   （3）找到第二個非葉節(jié)點4，由于[4,9,8]中9元素最大，4和9交換
   
   image.png
   
   （4）這時，交換導(dǎo)致了子根[4,5,6]結(jié)構(gòu)混亂，繼續(xù)調(diào)整，[4,5,6]中6最大，交換4和6
   
   image.png
   
   

   （5）此時，我們就將一個無序序列構(gòu)造成了一個大頂堆

2. 步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進行交換、重建、交換
   （1）將堆頂元素9和末尾元素4進行交換

   
   
   image.png
   
   

   （2）重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義

   
   
   image.png
   
   （3）再將堆頂元素 8 與末尾元素 5 進行交換，得到第二大元素 8
   
   image.png
   
   （4）后續(xù)過程，繼續(xù)進行調(diào)整，交換，如此反復(fù)進行，最終使得整個序列有序
   
   image.png
3. 步驟總結(jié)：
   1).將無序序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆
   2).將堆頂元素與末尾元素交換，將最大元素"沉"到數(shù)組末端
   3).重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個序列有序

5、代碼

**
 * title: 堆排序(大頂堆案例--800W數(shù)據(jù)測試
 * @author 阿K
 * 2021年1月2日 下午11:22:55 
 */
public class HeapSort {

    public static void main(String[] args) {
        // 要求將數(shù)組進行升序排序
//      int arr[] = {4, 6, 8, 5, 9};
//      heapSort(arr);
//      System.out.println(Arrays.toString(arr));

        // 800w 數(shù)據(jù)測試
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數(shù)
        }
        long time1 = System.currentTimeMillis();
        heapSort(arr);
        long time2 = System.currentTimeMillis();
        System.out.println("堆排序?qū)崿F(xiàn)大頂堆排序800W數(shù)據(jù)：" + (time2 - time1) + "毫秒");
    }
    
    /**
     * 構(gòu)建堆排序(最終調(diào)用)
     * @param arr 傳入的數(shù)組
     */
    public static void heapSort(int[] arr) {
        int temp = 0;

        // 分步測試
//      adjustHeap(arr, 1, arr.length);
//      System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6
//      adjustHeap(arr, 0, arr.length);
//      System.out.println("第二次" + Arrays.toString(arr)); // 9, 6, 8, 5, 4      

        // 完整步驟
        // 將無序序列構(gòu)建成的一個堆，根據(jù)升序或者降序，選擇大頂堆或者小頂堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        // 將堆頂元素與末尾元素交換，將最大元素 "沉"到數(shù)組末端
        // 重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，（就這樣反復(fù)執(zhí)行 【調(diào)整 -> 交換】，直到整個序列有序）
        // 時間復(fù)雜度 為線性 O(nlogn)
        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
    }
    
    /**
     * 將一個數(shù)組（二叉樹），調(diào)整成一個大頂堆
     * 功能：完成將 以 i 對應(yīng)的非葉子節(jié)點的樹調(diào)整成大頂堆
     * eg：第一次：int arr[] = {4, 6, 8, 5, 9}; => adjustHeap(i=1) => 得到 {4, 9, 8, 5, 6}
     * eg：第一次：int arr[] = {4, 9, 8, 5, 6}; => adjustHeap(i=0) => 得到 {9, 6, 8, 5, 4}
     * @param arr       待調(diào)整的數(shù)組
     * @param i         表非葉子節(jié)點在數(shù)組中的索引
     * @param length    表對多少個元素進行調(diào)整（length會逐漸減少，因為被調(diào)整好的增加了）
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        // 先取出當(dāng)前元素的值，報錯在臨時變量中
        int temp = arr[i];

        // 開始調(diào)整
        // 故：k = 2*i+1; 表示 k 是 i節(jié)點的左子節(jié)點
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {// k=2*k+1 ,k 左子節(jié)點的左子節(jié)點
            if (k + 1 < length && arr[k] < arr[k + 1]) {// 說明左子節(jié)點的值，小于右子節(jié)點的值
                k++;// k 指向右子節(jié)點
            }
            if (arr[k] > temp) {// 若子節(jié)點大于父節(jié)點的值
                arr[i] = arr[k]; // 把較大的值賦值給當(dāng)前節(jié)點
                i = k;// 指向 k,繼續(xù)比較(移動)
            } else {
                break;
            }
        }
        // 當(dāng)for 循環(huán)結(jié)束后,已經(jīng)將以 i 為父節(jié)點的樹的最大值，放在最頂點(局部)
        arr[i] = temp;// 將 temp放到調(diào)整后的位置
    }
}

6、性能測試和總結(jié)

1. 作者的機子平均在 2000 - 2300 毫秒

   
   
   image.png
2. 可見速度相當(dāng)快，平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序

7、參考文章

https://www.cnblogs.com/chengxiao/p/6129630.html