堆排序

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

根据数组脑补出一颗完全二叉树：

对于数组中下标为i的节点：

左孩子下标：2i + 1

右孩子下标：2i + 2

父节点：(i - 1) / 2

务必牢记上述关系！

什么是堆？

堆就是一棵完全二叉树。

大根堆：任何一棵子树的最大值都是这棵子树的头部。

小根堆：任何一棵子树的最小值都是这棵子树的头部。

把一个数组转化成大根堆：

heapInsert方法：

从0开始逐步扩大范围，根据父节点下标 = (i - 1) / 2将当前值与父节点比较，如果比父节点大就和父节点交换，直到不比父节点大为止。关键：上浮。

public static void heapInsert(int[] arr, int index){
    while(arr[index] > arr[(index - 1) / 2]){
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

调整大根堆：

heapify方法：

如果大根堆中某一个位置元素值减小，则该元素和其左右孩子中较大的那个交换，重新调整为大根堆。关键：下沉。

public static void heapify(int[] arr, int index, int heapSize){
    int left = 2 * index + 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 = 2 * index + 1;
    }
}

堆排序：

• 将数组建立成大根堆

• 每次把堆顶元素都和大根堆的最后一个元素交换

• heapSize - 1，执行heapify方法

• 循环至heapSize为0

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);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while(heapSize > 0){
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    /**
     * 将数组转化为大根堆的关键-----------上浮
     * */
    public static void heapInsert(int[] arr, int index){
        while(arr[index] > arr[(index - 1) / 2]){
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 数组中若有数变小，调整大根堆-------下沉
     * 可用于弹出堆的一个元素：将堆中最后一个元素与堆顶元素交换，然后heapsize - 1，从0位置上开始执行此方法
     * */
    public static void heapify(int[] arr, int index, int heapSize){
        int left = 2 * index + 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 = 2 * index + 1;
        }
    }

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 4, 5, 8, 5, 10, 2};
        HeapSort(arr);
        for(int i = 0; i < arr.length; ++i){
            System.out.print(arr[i] + " ");
        }
    }
}

关于堆排序，这里有个动图可以加深一下理解：

堆结构非常重要

• 堆结构的heapInsert和heapify
• 堆结构的增大和减少
• 如果只是建立堆的过程，时间复杂度为O(N)
• 优先级队列结构就是堆结构