数据结构与算法学习总结--堆及其应用

什么是堆

堆是一个完全二叉树 堆的每个节点的值都大于等于（或者小于等于）它的子树中每个节点的值（实际上等价于堆的每个节点的值都大于等于（或者小于等于）它的左右子节点的值）

每个节点值都大于等于左右子树节点值的堆，称为大顶堆 每个节点值都小于等于左右子树节点值的堆，称为小顶堆

如何存储堆

堆是一个特殊的树，因此可以使用树的存储结构（数组，链表结构来存储）来存储 因为堆是完全二叉树，因此用数组来存储，实现更简单、高效、节省内存（在数组中节点下标为i的节点，其左子节点下标为i2，右子节点下标为i2+1，父节点下标为i/2）

堆的常用操作（以大顶堆为例）

插入元素

在末尾插入（插入到最后的叶子节点上），然后顺着节点到根节点的路径，进行堆化。（堆化，就是比较子节点与父节点的大小关系，看是否满足堆定义中的大小关系，如果不满足，就交换父子节点，接着再往上进行，直到根节点或者满足条件为止，如果满足，则堆化结束） 时间复杂度O(logn)

删除堆顶元素

将末尾的元素替换掉堆顶的元素，然后进行从上到下的堆化（从根节点到叶节点） 从上到下的堆化：比较父子节点之间的大小关系，看是否满足堆的定义，如果不满足，交换父子节点，直到叶节点或者满足条件为止 时间复杂度O(logn)

如何基于堆，实现堆排序

堆排序分为两个过程：建堆和排序

建堆过程

从下标为n/2的节点开始，从后往前，进行自上往下的堆化过程，完成之后，即可得到一个大顶堆，该过程时间复杂度为O(n)

排序过程

建堆完成之后，堆顶元素即为最大元素，把堆顶元素与最后一个元素交换，最大的元素就排到了位置n上，然后进行自上往下的堆化操作，堆化完成后（相当于剩余的n-1个元素又重新构成了一个新的大顶堆），再取堆顶元素，放到下标为n-1的位置，一直重复这个过程，直到最后只剩一个元素

堆排序的时间复杂度O(nlogn),空间复杂度O(1)，堆排序不是稳定的排序算法

为什么快排比堆排序性能好

堆排序算法性能非常稳定，最好、最差、平均时间复杂度都是O（nlogn）,而快排最坏时间复杂度会退化为O(n^2)，那为什么反而是快排的性能好呢？主要原因是： 1、堆排序访问数据的方式没有快排好（快排是顺序访问数据，对于cpu缓存友好，堆排序是跳跃着访问数据（堆化）） 2、对于同样的数据，堆排序交换数据的次数比快排多

堆的常见应用

优先级队列（Java中的PriorityQueue、C++中的priority_queue）

一个堆就可以看作是一个优先级队列 往队列中插入元素就相当于往堆中插入元素 从队列中取出优先级最高的元素就相当于取出堆顶元素 优先级队列应用：合并有序小文件、高性能定时器

Top K问题

维护一个大小为K的小顶堆（或者大顶堆），即可解决Top K问题

利用堆求中位数（或者其他百分位的数据）

维护两个堆，一个大顶堆，一个小顶堆，并且小顶堆中的元素都大于大顶堆中的元素，插入数据时，不断调整两个堆中元素个数，使两个堆的元素个数相当，此时大顶堆的元素就是中位数