堆排序

作者: gyl_coder | 来源:发表于2018-01-02 22:10 被阅读8次
    mmexport1520334289708.gif

    阅读原文

    堆排是基于堆的一种排序算法,对于堆的了解,请看什么是堆排序(如果对堆的插入和删除不清楚,强烈建议先看堆),今天我们聊聊堆排的思想,复杂度以及稳定性。

    堆排思想

    前情回顾:克给谦子解决了时间管理上的问题:什么是堆排序

    过了几天后,谦子高兴地跑到老师跟前

    1.png

    早知不来了,谦子心想

    2.png

    谦子心想:上次去溪边游玩不是已经出过这个题吗,当时学会了冒泡排序,这次肯定不是那么简单,肯定和前几天的堆有关系

    3.png

    删除中交换操作会破坏堆有序
    但下沉操作会重新调整堆

    谦子画了一个图解释道

    4.png
    5.png

    删除包括三个步骤:
    ① 交换堆顶与堆最后一个元素
    ② 堆大小(heapSize)减一
    ③ 调整堆(sink(arr,1))
    具体讲解请看:二叉堆

    6.png

    建堆

    7.png

    上浮(swim)操作会保持堆有序

    8.png 9.png 10.png 11.png 12.png 13.png 14.png

    注意:在下沉(sink)某个节点的时候,这个节点的两个孩子必须是堆

    堆排代码

    15.png

    克突然话锋一转

    16.png

    又要写代码,谦子心想,虽说心中这样想,但还是要写的,思考了一会,只见谦子写下了如下代码

    /**
    * 将传进来的无序数组变成小根堆
    * @param arr a[1...n]为有效元素,a[0]为无效元素
    */
    public void buildHeap(int[] arr) {
        // 从第一个非叶子节点开始sink调整,也就是堆大小的一半处
        for(int i = heapSize/2; i >= 1; i --) {
            sink(arr, i); // 调整以节点i为父节点的树为堆(符合堆有序)
        }
    }
    
    17.png

    谦子解释道

    18.png

    过了一会谦子又写出了删除最小值的代码

    /**
    * 删除堆中最小的元素(通过heapSize--逻辑上删除)
    * @param arr a[1...n]为有效元素,a[0]为无效元素
    */
    private void deleteMin(int[] arr) {
        // 交换堆顶和堆最后一个元素
        swap(arr, index1, heapSize); 
        heapSize --;
        sink(arr, parentIndex:1); // 调整使之重新变成堆有序
    

    }

    19.png

    前两个都写出来了,剩下的排序就很简单了,按照之前的思路,先建立一个小根堆,然后不断地删除堆顶最小元素,删除N-1次就OK了

    /**
    * 对给定数组arr排序,使之为降序
    * @param arr a[1...n]为有效元素,a[0]为无效元素
    */
    public void heapSize(int[] arr) {
        int N = arr.length-1;
        buildHeap(arr);    // 建小根堆
        // n个元素的小根堆,排序(删除堆顶)n-1次,数组就变成降序了
        for(int i = 1; i <= n-1; i ++) {
            deleteMin(arr);   // 删除arr数组中最小的值
        }
    }
    
    20.png

    谦子解释道

    21.png

    谦子暗自惊叹老师的功力,不知不觉又学到了一个排序方法

    时间复杂度

    22.png

    看到数学头疼的可以直接跳过看结论

    谦子还没缓过神,又来了一个最让他头疼的时间复杂度

    23.png

    克拿出了笔和纸

    24.png

    建堆时间复杂度

    25.png

    叶子节点高度为0,下沉代价为0

    谦子目不转睛地

    26.png

    所以问题变为:
    ① 高度最高多高(高度上界)
    ② 高度h有多少节点
    这里你记住两个结论

    29.png 30.png 31.png 32.png

    谦子长舒一口气

    n-1次删除 复杂度

    33.png

    n-1次调用deleteMin
    deleteMin中包含 swap操作和 sink操作
    swap操作代价为常数,sink操作代价为lgn,swap操作相对于sink操作可以忽略不计
    则相当于进行了n-1次sink操作
    则一共花费的代价为:(n-1)*lgn ~ nlgn
    故时间复杂度为O(nlgn)

    34.png

    稳定性

    35.png

    谦子说着说着画了一个图

    36.png 37.png

    摘录自:趣谈编程

    相关文章

      网友评论

        本文标题:堆排序

        本文链接:https://www.haomeiwen.com/subject/kwyjgxtx.html