11.堆排序

堆排序，形成的堆就是一顆完全二叉樹 ¹

堆排序用于很多貪心演算法的問題中

以陣列形式表示二叉樹

下標i的左孩子是2i+1，右孩子是2i+2，一個節點的父節點是(i-1)/2

大根堆

在這棵完全二叉樹中任何一棵子樹的最大值是頭部

建立大根堆

給一個陣列：2 1 3 6 0 4

我們首先人為規定這棵樹只有一個節點2，依次增加一個節點并調整為大堆程序如下：演示程序使用graphviz，一個圖一份原始碼

1

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('2', '2')

2

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('2', '2')
dot.node('1', '1')
dot.edges(['21'])

3

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('2', '2')
dot.node('1', '1')
dot.node('3', '3')
dot.edges(['21', '23'])

調整: 3和2節點交換

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('3', '3')
dot.node('1', '1')
dot.node('2', '2')
dot.edges(['32', '31'])

4

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('3', '3')
dot.node('1', '1')
dot.node('2', '2')
dot.node('6', '6')
dot.edges(['31', '32', '16'])

調整之后：

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('6', '6')
dot.node('3', '3')
dot.node('2', '2')
dot.node('1', '1')
dot.edges(['63', '62', '31'])

5

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('6', '6')
dot.node('3', '3')
dot.node('2', '2')
dot.node('1', '1')
dot.node('0', '0')
dot.edges(['63', '62', '31', '30'])

6

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('6', '6')
dot.node('3', '3')
dot.node('2', '2')
dot.node('1', '1')
dot.node('0', '0')
dot.node('4', '4')
dot.edges(['63', '62', '31', '30', '24'])

調整之后：

from graphviz import Digraph
dot = Digraph(comment='The Round Table')
dot.node('6', '6')
dot.node('3', '3')
dot.node('2', '4')
dot.node('1', '1')
dot.node('0', '0')
dot.node('4', '2')
dot.edges(['63', '62', '31', '30', '24'])

此時大根堆陣串列示為：6 3 4 1 0 2

如上程序展示了建立大根堆的詳細程序，代碼如下：

package yzy.algorithm;
//大根堆
public class heapSort {
    public static void heapSort(int[] arr){
        if(arr == null || arr.length<2)
            return ;
        for(int i=0; i<arr.length; ++i)
            heapInsert(arr, i); // 0~i
    }
    public static void swap(int[] arr, int index1, int index2){
        arr[index1] ^= arr[index2];
        arr[index2] ^= arr[index1];
        arr[index1] ^= arr[index2];
    }
    //調整新增節點
    public static void heapInsert(int[] arr, int index) {
        while(arr[index] > arr[(index-1)/2]) { //精華陳述句，考慮了index=0時while終止
            swap(arr, index, (index - 1) >> 1);
            index = (index - 1) / 2;
        }
    }
    //陣列中一個元素值發生變化，則調整使其繼續成為大根堆
    public static void heapify(int[] arr, int index, int heapSize) {  //[0, heapSize]范圍上形成的堆
        int left = index*2+1;
        while(left < heapSize){
            int largest = left + 1 < heapSize && arr[left+1] > arr[left]
                    ? left + 1
                    : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if(largest == index)
                break;
            swap(arr, largest, index);
            index = largest;
            left = index*2+1;
        }
    }

    public static void showArr(int[] arr){
        int i = 0;
        while(i<arr.length)
            System.out.print(arr[i++]);
        System.out.println();
    }
    public static void main(String[] args) {
        int arr[] = {2, 1, 3, 6, 0, 4};
        showArr(arr);
        heapSort(arr);
        showArr(arr);
    }
}

建立大根堆的復雜度

每加入一個節點的時間復雜度就是，在加入這個節點之前完全二叉樹的高度，在加入第i個節點時，時間復雜度就是
l o g 2 ( i ? 1 ) log_2(i-1) log2?(i?1)
建立N個節點的大堆的程序時間復雜度就是
l o g 2 1 + l o g 2 2 + l o g 2 3 + . . . + + l o g 2 N ? 1 log_2 1+log_2 2+log_2 3+...++log_2 N-1 log2?1+log2?2+log2?3+...++log2?N?1
收斂于N，最終時間復雜度就是O(N)

彈出大根

使用一個變數heapSize人為規定大根堆的大小，堆頂和最后一層最右的葉節點交換并且heapSize減一則表示彈出堆頂元素，heapify用于index位置節點改變的情況下調整二叉樹依然為大根堆

package yzy.algorithm;
//大根堆
public class heapSort {
    public static void heapSort(int[] arr){
        if(arr == null || arr.length<2)
            return ;
        for(int i=0; i<arr.length; ++i)
            heapInsert(arr, i); // 0~i
    }
    public static void swap(int[] arr, int index1, int index2){
        arr[index1] ^= arr[index2];
        arr[index2] ^= arr[index1];
        arr[index1] ^= arr[index2];
    }
    //調整新增節點
    public static void heapInsert(int[] arr, int index) {
        while(arr[index] > arr[(index-1)/2]) { //精華陳述句，考慮了index=0時while終止
            swap(arr, index, (index - 1) >> 1);
            index = (index - 1) / 2;
        }
    }
    //陣列中一個元素值發生變化，則調整使其繼續成為大根堆
    public static void heapify(int[] arr, int index, int heapSize) {  //[0, heapSize]范圍上形成的堆
        int left = index*2+1;
        while(left < heapSize){
            int largest = left + 1 < heapSize && arr[left+1] > arr[left]
                    ? left + 1
                    : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if(largest == index)
                break;
            swap(arr, largest, index);
            index = largest;
            left = index*2+1;
        }
    }
    public static void showArr(int[] arr){
        int i = 0;
        while(i<arr.length)
            System.out.print(arr[i++]);
        System.out.println();
    }
    public static void main(String[] args) {
    //建立大根堆
        int arr[] = {2, 1, 3, 6, 0, 4};
        showArr(arr);
        heapSort(arr);
        showArr(arr);


        System.out.println("彈出大根堆頂級大根");
//        彈出大根
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);  // 先將大根和最后一層最右的葉節點交換，heapSize同時減1
        heapify(arr, 0, heapSize);  // 將[0,heapSize)調整為大根堆
//      此時相比之前根彈出，有效大根堆范圍時[0,heapSize)
        showArr(arr);


        System.out.println("回圈依次彈出：");
//      回圈依次彈出
        while(heapSize>0){
            swap(arr, 0, --heapSize);
            heapify(arr, 0, heapSize);
            showArr(arr);
        }
    }
}

觀察以上彈出堆頂元素的操作，如果依次彈出堆頂元素直到人為規定的堆大小heapSize為0，就會發現陣列元素從小到大依次有序，小根堆則同樣可以使陣列元素從大到小有序

掌握彈出堆頂元素，可以巧妙的解決很多問題，并且加速很多問題的演算法時間復雜度，請繼續觀看后續博文