GingerBear
搞定Heap这个数据结构
看了Wikipedia后，我来写一下另一个不用排序的方法求第K大的元素，使用Heap这个数据结构。
先说说Heap
Heap是一种树状的数据结构，和普通的树不同，Heap有这样一个特点：就是所有的**“爸爸对于自己的儿子的大小关系”都一样，拿最常见的complete binary max-heap举例的话，就是，只要爸爸比自己的两个儿子大就可以，如果出现侄子比阿姨**大的话也没关系，最顶上的老祖宗总是最大，如下图。
complete binary max-heap还有一个特点就是，它是一个完全树 (complete tree)，意思就是这棵树必须是尽可能向左挤满，所以空缺永远出现在最右下方。
Heap有两种操作，insert和delete。
Insert
因为是完全树，所以必须先从右下角往左做挤进去，找到位置后跟爸爸比较，如果比爸爸大，那就互换，直到比爸爸小才停止。
Delete
这个delete指的是把老祖宗root干掉，然后选出另一个老祖宗。巧妙地做法是，把最右下角那个孙子放到老祖宗的位置，然后跟老祖宗的“大儿子”互换，直到这孙子放到合适的位置为止。
对于Insert和Delete操作，时间复杂度都是O(log n)，试着推导一下。
不管是Insert还是Delete，都是上下层之间的比较，所以最多的“比较后互换”操作的次数（老祖宗其实是小孙子）就是总层数。
对于一个L层的二叉树，树的长度 n = 2^0 + 2^1 + 2^2 + ... + 2^(L-1)
根据等比数列求和公式，n = 2^L - 1
所以，L = log2(n + 1)
所以最坏情况就是就是log2(n + 1)次操作，即O(log n)。
Heap的实现
跟一般的Tree不同，complete binary max-heap一般用数组来实现，第一个元素表示老祖宗，接着两个元素表示老祖宗的两个儿子，接着四个元素表示四个孙子，以此类推。能用数组这么表示的原因是因为heap是完全树，中间不会有空缺，空缺只出现在最后。
建立一个Heap
笨的办法就是一个一个**“从下往上”**insert，这需要O(n log n)，这好理解因为每次insert都需要O(log n)，insert n个元素，那就是O(n log n)了。
比较好的办法是，反过来，用delete里的**“从上往下”**的方法。具体说，就是把一个普通的完全二叉树，从最底层的那些（只有儿子没有孙子）小树苗们开始，比较爸爸与他的两个儿子，与大的儿子互换。等所有的小数苗都变成小Heap了，再开始从他们上一级的爸爸开始与小Heap们进行“比较后互换”，如果爸爸比儿子小，互换后还得跟孙子比，直到比他们都大。这样下去，一直到那个最高位的“所谓的老祖宗”也找到自己的位置。
这样可以优化到O(n)，这里引用Wiki的推导：
对于从下往上数第h层的某个爸爸，它最坏（自己才是小孙子）需要进行h次与儿子孙子们的“比较后互换”（别忘了他的儿子们都已经成heap了）才能找到自己真正的位置，所以第h层的一个爸爸找到合适的位置的复杂度也就是O(h)。
之前算过，如果树有n个元素的话，树的总层数是log2(n + 1)，这里简称lg(n)，那么第h层就有2^(lg(n) - h - 1)，这个好理解，因为最高层有2^0个爸爸，第二高层是2^1个爸爸，那么“从下往上第h层”就应该是的2^( lg(n) - h - 1 )个爸爸了。
2^( lg(n) - h - 1 )变换一下就是n / ( 2^(h - 1) )，为啥要变换？主要是为了下面写起来方便。
好，有了第h层的爸爸的个数n / ( 2^(h - 1) )，有了第h层一个爸爸找到位置的时间O(h)，有了总共的层数lg(n)，接下来就可以算算所有的爸爸找到合适位置的总时间了，也就是我们想要知道的**“时间复杂度”**。
这里给出一个看似牛逼的公式：
实际上不复杂，就是**“某一层的爸爸个数”乘以“一个爸爸要话的时间”根据“层数”**累加起来，唯一复杂的就是 h / 2^h 无限趋近于2。
用Heap来求第K大的元素
看到这里应该和明白怎么求第K大的元素了，首先把数组变成一个Heap，然后delete操作（或者叫pull操作）K次得到的就是第K大得结果。
时间复杂度是建立Heap的时间加上K次delete操作的时间，即 O(n) + K * O(log n) K最坏是N，所有最终结果是O(n log n)。
我去年期末老师有简单的介绍一下heap. 我印象中生成max heap/min heap 然后再一个一个delete这个过程就叫heap sort.
