算法基础--堆排序

目录

• 堆的结构

• 满二叉树

• 完全二叉树

• 数组与完全二叉树

• 大根堆&&小根堆

• 用数组，建立大根堆二叉树

• 向下调整

• 堆排序

堆的结构

堆实际上是一颗完全二叉树形式的数组

满二叉树

除最后一层无任何子 节点 外，每一层上的所有结点都有两个子结点二叉树。

满二叉树属于完全二叉树

完全二叉树

在满二叉树的基础上，最后一层所有的结点都连续集中在最左边，这就是完全二叉树。

• 数组与完全二叉树

如果从下标从1开始存储，则编号为i的结点的主要关系为：

双亲：下取整 （i/2）

左孩子：2i

右孩子：2i+1

如果从下标从0开始存储，则编号为i的结点的主要关系为：

双亲：下取整 （(i-1)/2）

左孩子：2i+1

右孩子：2i+2

这个规律，通常用来对通过指定下标取得相关节点下标。

大根堆&&小根堆

处理最值问题时，堆的调整复杂度远低于其他结构。

• 大根堆

任一节点的关键码均大小于等于它的左右孩子的关键码，位于堆顶节点的关键码最大

• 小根堆

任一节点的关键码均小于等于它的左右孩子的关键码，位于堆顶节点的关键码最小。

• 优先级队列 用大小堆的方式更容易实现

如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。

对于这种最值问题，堆的调整复杂度远低于其他结构。

而使用大根堆的方式，每次新入队元素最多只需要堆整个结构进行LogN次的调整，便可以让堆结构重归有序。

40亿的量级甚至只需要32次调整就可以实现。

用数组，建立大根堆二叉树

将数组中元素依次放入完全二叉树中，若大于父节点则依次比对交换。保证时刻处于大根堆排序

第i个数字被插入时 排序 的时间复杂度与高叉树高度相等，即O(Logi)。

所有数字都插入依次的时间复杂度收敛于 O(N)

//大根堆排序
func maximumHeapSort(arr:inout [Int]) {
    if arr.count < 2 {
        return
    }
    //大根堆排序
    for i in 0.. arr[parentIndex] {
        arr.swapAt(currentIndex, parentIndex)
        currentIndex = parentIndex
        parentIndex = (currentIndex - 1)/2
    }
    
}

向下调整

在一个大根堆中，某个位置的数被改变（并且变小）了。重新对堆数组进行调整

比对该位置与其左右子节点，并且与较大的一个进行交换，依次向下进行。

func heapify (arr:inout Array,index:Int,heapSize:Int){
    var currentIndex = index;
    var left=2*currentIndex+1//左节点位置
    var right=left+1//右节点位置
    var largest = currentIndex //最大位置暂定为current
    while leftarr[currentIndex] ? largest:currentIndex
        
        if largest == currentIndex {
            break //如果当前已经为最大位置，则结束
        }
        
        arr.swapAt(currentIndex, largest)//交换当前位置与左右两端最大位置
        
        currentIndex = largest//将当前位置下移
        left=2*currentIndex+1//左节点新位置
        right=left+1//右节点新位置
    }
}

堆排序

先构建出一个大根堆，然后依次将头部最大值转移到有效数组的最后一位，并且将排序区域前移。

func heapSort(arr:inout [Int]) {

maximumHeapSort(arr:&arr)//先构建出一个大根堆

let size = arr.count

其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

最后

本文主要是自己的学习与总结。如果文内存在纰漏、万望留言斧正。如果愿意补充以及不吝赐教小弟会更加感激。

参考资料

作者：kirito_song

链接：https://www.jianshu.com/p/3decfc83a40a