博客详情

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

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

计算公式：

左孩子：i * 2 + 1;

右孩子：i * 2 + 2；

父节点：(i - 1) / 2.

堆主要有两个操作：

添加元素，并维持堆的性质-heapInsert；每次添加元素时：都和该节点的父节点进行比较，如果比父节点大，则和父节点进行交换；否则循环结束；此外，如果该节点已经是父节点，循环结束。注：（0 - 1） / 2 的结果为0。

    //arr[0...index - 1]已经是大根堆了，某个数现在处在index位置，往上继续上浮
    //arr[0...index]都是大根堆
    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。某个数在index位置，看看能否下沉，不断和左右两个孩子比较，较大的孩子如果大于当前的父节点，父节点下沉，较大孩子上浮，周而复始。

    //某个数在index位置，看看能否下沉，
    //不断和左右两个孩子比较
    //较大的孩子如果大于当前的父节点，父节点下沉，较大孩子上浮，周而复始
    public static void heapify(int[] arr, int index, int heapSize){
        int left = index * 2 + 1; //左孩子的下标
        while (left < heapSize){ //下方还有孩子的时候
            //两个孩子中，谁的值大，把下标给largest
            int largest = (left + 1 < heapSize && arr[left + 1] > arr[left]) ? left + 1 : left;
            //父节点和较大的孩子之间，谁的值大，把小标给largest
            largest = (arr[index] > arr[largest]) ? index : largest;
            if(largest == index)
                break;
            swap(arr,index,largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

使用堆进行排序：

public static void heapSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    //O(N * logN)
    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 class MyHeap {

    private myHeap() {}


    public static void heapSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        //O(N * logN)
        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);
        }
    }

    //arr[0...index - 1]已经是大根堆了，某个数现在处在index位置，往上继续上浮
    //arr[0...index]都是大根堆
    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;
        }
    }

    //某个数在index位置，看看能否下沉，
    //不断和左右两个孩子比较
    //较大的孩子如果大于当前的父节点，父节点下沉，较大孩子上浮，周而复始
    public static void heapify(int[] arr, int index, int heapSize){
        int left = index * 2 + 1; //左孩子的下标
        while (left < heapSize){ //下方还有孩子的时候
            //两个孩子中，谁的值大，把下标给largest
            int largest = (left + 1 < heapSize && arr[left + 1] > arr[left]) ? left + 1 : left;
            //父节点和较大的孩子之间，谁的值大，把小标给largest
            largest = (arr[index] > arr[largest]) ? index : largest;
            if(largest == index)
                break;
            swap(arr,index,largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

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

    // 判断 arr 数组是否有序
    private static boolean isSort(int[] arr){
        int len = arr.length - 1;
        for ( int i = 0 ; i < len ; i ++ ){
            if(arr[i] > arr[i + 1])
                return false;
        }
        return true;
    }

    // 测试 HeapSort
    public static void main(String[] args) {
        //生成随机数组
        int N = 1000000;
        int[] arr = new int[N];
        int rangeR = 0;
        int rangeL = 100000;
        for (int i = 0; i < N; i++)
            arr[i] = (int)(Math.random() * (rangeR - rangeL + 1) + rangeL);
        Long startTime = System.currentTimeMillis();
        //使用堆排序进行排序
        myHeap.heapSort(arr);
        Long endTime = System.currentTimeMillis();
        System.out.println("heapSort:" + (endTime - startTime) / 1000.0 + "s");
        //判断数组是否有序
        System.out.println(isSort(arr));
    }
}

测试结果：

heapSort:0.246s
true

注：代码参考了左程云老师讲课的视频视频地址：牛客基础算法入门班

原创

堆排序（Java版）

评论 null 条