什么是堆？

• 堆是一种特殊的树，只要满足以下两个条件，就可以称这棵树为堆

  • 堆是一颗完全二叉树（完全二叉树要求，除了最后一层，其他节点个数都是满的，最后一层的节点都靠左排列）

  • 堆中的每一个节点都必须大于等于(或者小于等于)其子树中每个节点的值。

• 每个节点的值都大于等于其子树每个节点的值的堆，我们称之为大顶堆，每个节点的值都小于等于其子树每个节点的值的堆，我们称之为小顶堆。如下图：

• 从上图可以看出，对于同一组数据，我们可以构建多种不同形态的堆。

如何存储堆？

• 堆是一颗完全二叉树，比较适合用数组存放，因为用数组存放不需要存储左右子节点的指针，非常节省空间，通过下标就可以找到一个节点的左右子节点和父节点。下图就是一个数组存放堆的例子：

• 从图中可以看出，下标i的节点的左子节点的下标是i2，右子节点的下标为i2+1，父节点的下标为i/2，这是根节点存放在下标1的位置时的规律。

堆的插入和删除

• 我们对堆做删除或插入操作后，可能会破坏堆的两大特性，我们就需要进行调整，使其重新满足堆的两大特性，这个过程，我们称之为堆化(heapify)，堆化有两种：从下往上堆化和从上往下堆化。
• 往堆中插入一个元素，我们可以用从下往上堆化，就是从下开始顺着节点路径往上走，进行比较，然后交换。例如：往堆中插入元素22，如下图：

//自定义一个堆，并且插入数据
public class Heap{
    private var array:Array<Int>     //存放堆的数组
    private var maxCount: Int        //堆数组可以存储的最大个数
    private var realCount: Int = 0   //堆数组实际存储的数据个数
    
    //初始化一个堆，给定堆的容量
    public init(capacity: Int){
        array = Array(repeating: 0, count: capacity)
        maxCount = capacity
        realCount = 0
    }
    
    public func insert(data: Int){
        if realCount >= maxCount { return } //堆满了
        realCount = realCount + 1
        var i = realCount
        array[i] = data    
        // i/2代表i的父节点
        while(i / 2 > 0 && array[i] > array[i / 2]){    //当节点比其父节点小时，进行交换，这就是从下而上堆化的过程
            array.swapAt(i, i/2)
            i = i / 2
        }
    }
}

var testHeap = Heap(capacity: 10)
testHeap.insert(data: 5)

• 删除堆顶元素，我们可以采用从上往下堆化，为了避免删除后，堆是不完全二叉树，我们将堆顶元素删除后，要将最后一个元素放到堆顶，然后在进行堆化。例如：我们想删除堆顶元素33，就需要删除33后，将最后一个元素放在堆顶，然后进行堆化，过程如下：

    //删除堆顶元素
    public func removeMax(){
        if realCount == 0 { return }    //如果堆中没有元素
        array[1] = array[realCount]
        realCount = realCount - 1
        heapify(array: array, realCount: realCount, i: 1)
    }
    
    private func heapify(array:Array<Int>, realCount: Int, i: Int){
        var headArray = array
        var i = i
        while true {
            if 2*i < realCount && headArray[i] < headArray[2*i]{
                //如果节点小于其左子节点
                headArray.swapAt(i, 2*i)
                i = 2*i
            }else if 2*i+1 < realCount && headArray[i] < headArray[2*i + 1]{
                //如果节点小于其右子节点
                headArray.swapAt(i, 2*i+1)
                i = 2*i + 1
            }else{
                break
            }
        }
    }

• 一个包含n个节点的完全二叉树，树的高度不会超过log2n，堆化的过程是沿着节点路径走的，最多不会超过树的高度，所以堆化的时间复杂度是跟树的高度成正比的，也就是O(logn)；插入和删除堆顶元素主要逻辑就是堆化，所以插入和删除堆顶元素的时间复杂度就是O(logn)

如何用堆实现堆排序？

• 我们学过很多排序算法，有时间复杂度为O(n2)的冒泡排序、插入排序、选择排序，也有时间复杂度为O(nlogn)的归并排序、快速排序。借用堆这种数据结构实现的排序，我们称之为堆排序，堆排序的时间复杂度非常稳定，是O(nlogn)，而且还是原地排序算法。
• 堆排序的过程可以分解成两个大步骤：建堆和排序
• 首先，进行建堆，就是在不借助其他数组的前提下，将数组原地建成一个堆，思路是这样，从第一个非叶子节点开始，不断往上依次堆化，如下图，建堆的时间复杂度是O(n)

• 然后，进行排序，建堆后数据就按照大顶堆的特性排布了，数组中的第一个元素就是堆顶，也是最大的元素，接下来的排序我们这样处理：将堆顶元素与最后一个元素交换，然后除了最后一个元素以外的n-1个元素进行堆化，然后再将堆顶元素与倒数第二个元素交换，然后将除了最后两个元素以外的n-2个元素堆化，一直重复这个过程，知道堆中只剩下下标为1的元素，排序就完成了。我们举个例子说明一下，如下图所示

总结一下

• 堆排序的过程只需要个别临时存储空间，所以是原地排序算法；

• 堆排序包括两个步骤：建堆和排序，建堆时间复杂度是O(n)，排序时间复杂度是O(nlogn)，所以堆排序整体的时间复杂度是O(nlogn)；

• 由于堆排序过程中存在堆顶元素和最后一个节点互换的操作，有可能改变原始相对顺序，所以堆排序不是稳定的排序算法

实际开发中，为什么快速排序比堆排序性能好？

• 堆排序数据访问方式没有快速排序友好，快排的数据时顺序访问的，而堆排序的数据时跳着访问的，所以堆排序对CPU缓存不友好。
• 对于同样的数据，堆排序的交换次数要比快速排序多。因为快速的交换次数是逆序度，而堆排序的建堆过程会打乱顺序，可能会更加无序，导致逆序度提高，所以堆排序交换次数更多一点。

堆的应用

堆这种数据结构有很多非常重要的应用，例如：优先级队列、求Top K、求中位数

优先级队列

• 优先级队列，顾名思义，它首先应该是一个队列，但是它不想前边讲的队列一样，是先进先出的，而是根据优先级来，优先级高的最先出队。
• 优先级队列的应用-将多个有序小文件合并成有序大文件，过程是这样的，分别从各个小文件中取一个字符串构建一个小顶堆，堆顶就是最小的字符串，将堆顶写入大文件后，将堆顶删除，然后继续从小文件中取出下一个字符串放入堆中，重新堆化成小顶堆，不断循环这个过程，直到把各个小文件取完。
• 优先级队列的应用-高性能定时器，用优先级队列我们就不需要每隔1s去扫描任务列表了，而是从优先级队列的队首（也就是小顶堆的堆顶）取出队首任务的执行时间，与当前时间做差值，得到时间间隔T，让定时器T秒后再来执行任务，执行完之后，在重新计算新的队首任务与当前时间的的差值，再次设定定时器。

利用堆求Top K

• 如何在一个包含n个数据的数组中，查找前K大数据呢？我们可以维护一个大小为K的小顶堆，然后顺序遍历数组，如果数据比堆顶大，则删除堆顶，将数据插入到堆顶，然后堆化；如果数据比堆顶小，则不作处理；遍历完成后，就可以得到前K大的数据了。

利用堆求中位数

• 对于n个数据的集合来说，以前的做法都是先排序，然后才能取到中位数，如果数据一直在动态变化，我们就需要不断的排序，成本就会很高了，而借助堆这种数据结构，我们就不用排序，就可以取到中位数。
• 我们需要维护两个堆，一个大顶堆，一个小顶堆，大顶堆存储前半部分数据，小顶堆存储后半部分数据，且小顶堆中的数据都大于大顶堆的数据，这样存储的话，大顶堆的堆顶就是我们要找的中位数了。例如：如下图所示，1、2、3、4、5、6、7这组数据的中位数就是4。

• 当新插入一个数据时，就可能会破坏我们前边的约定，我们可以这样处理：新插入的数据大于大顶堆的堆顶，就把新数据插入到小顶堆，否则就插入到大顶堆；总数据量为奇数时，大顶堆应该比小顶堆多一个，总数据量为偶数时，大顶堆应该和小顶堆的数据相同；按照这个规律，我们就把数据多的堆的堆顶移动至数据少的堆中。如下图：

• 利用一个大顶堆、一个小顶堆，我们就可以实现在动态的数据集合中快速求得中位数，这样做，在插入数据的时候需要涉及堆化，所以插入数据的时间复杂度变成了O(logn)，但是中位数就是大顶堆的堆顶，所以查找中位数的时间复杂度就优化成了O(1)。（虽然降低了插入的效率，但是提高了查找中位数的效率）