如醉如痴之最小堆
如醉如痴之最小堆
如醉如痴之最小堆
0.说在前面1.问题2.思考3.自虐4.回归5.总结6.作者的话
0.说在前面
一道简单的题，可以让你如醉如痴，更是因为这一道题，你才会学会很多，不要小看简单，简单中蕴含深意。
昨天碰到一道题，题目很简单，也是一个简单题，但是不导入库，实现起来就没那么简单了。。
当时一直在想，不要库怎么实现，就来学习堆的原理，然后去参考网上资料，开始动手实现了。
来个顺口溜：栈不是堆，堆不是栈，栈是堆栈，堆栈是栈，堆不是堆栈。
你晕了没，是不是有点绕~~
我们一起来看一下这道简单题，通过最小堆来实现。
由于这次问题，中文网站上没有，所有就在英文网站上。英文弱的克服一下，后面来大概说明一下意思。
1.问题
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Your KthLargest class will have a constructor which accepts an integer kand an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.
Example:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
Note:
You may assume that nums' length ≥ k-1 and k ≥ 1.
首先声明一个数组，然后给定一个k，寻找前k个数的最小值，比如[4,5,8,2]中，前三个数为4 5 8，最小为4，当后面的数比这个4大的时候就替换掉4，然后重新排序，选取三个中最小的，依此往后进行。
看到这个问题，对应的数据结构为堆排序中的最小堆！
实际就是利用最小堆去解决Top-k问题。
2.思考
这道题，先来一个简单的思路，通过导入库来实现。
这里要学习的库是heapq
这里用到的方法介绍：
heapq.heappush(heap, item) 把item添加到heap中（heap是一个列表）
heapq.heappop(heap) 删除堆顶元素，返回删除后的堆
heapq.heappushpop(heap, item) 先把item加入到堆中，然后再pop，比heappush()再heappop()要快得多
heapq.heapify(x) 将列表x进行堆调整，默认的是小顶堆
下面是参考的leetcode英文网站的discuss上面的两个实现思路：
【思路1】
对现有的数组堆进行调整，然后切割成两个list，第一个用来存储前k个元素所组成的堆，后一个用来存储其余元素，然后遍历一个list，从中找出大于第一个中最小的元素，然后通过heapq.heappushpop()方法，实现入堆，删除堆中最小元素，然后调整即可！
class KthLargest(object):
def __init__(self, k, nums):
self.k = k
self.heap = nums[:k]
heapq.heapify(self.heap)
rest = nums[k:]
for num in rest:
if num < self.heap[0]:
continue
heapq.heappushpop(self.heap, num)
def add(self, val):
if len(self.heap) < self.k:
heapq.heappush(self.heap, val)
elif val > self.heap[0]:
heapq.heappushpop(self.heap, val)
return self.heap[0]
【思路2】
这个思路跟前面差不多，区别在于前面的构造方法里面调用的函数不一样，下面这个比前面要稍微优一点，主要体现在，没有处理list分割，直接不断筛选出最后的堆，然后添加元素，选择即可！
class KthLargest(object):
def __init__(self, k, nums):
self.pool = nums
self.k = k
heapq.heapify(self.pool)
while len(self.pool) > k:
heapq.heappop(self.pool)
def add(self, val):
if len(self.pool) < self.k:
heapq.heappush(self.pool, val)
elif val > self.pool[0]:
heapq.heapreplace(self.pool, val)
return self.pool[0]
3.自虐
上面提到的方法，我感觉有点不真实。。竟然leetcode可以调第三方库，好吧。其实，我之前就知道可以调库，但是对于这道题我当时的思路是没有往调库方面想，就开始自虐模式，自己实现了一个heapq。
接下来，让我们一起来从最小堆理论分析，到最小堆实现过程。。
实现的方法有：
updateHeap() # 调整堆
heapify() # 创建堆同时调整堆
heappushpop() # 先把item加入到堆中，然后再pop，在调整堆
heappop() # 删除堆顶元素，返回删除后的堆
目的很简单，就是不用heapq，自己去实现heapq，然后再按照上面说的思路完成本题。
【数据结构定义】
这里初始化heapList，将第一个元素设为0，目的有两个，第一来防止为空，第二便于后面堆的调整！
def __init__(self):
self.heapList = [0]
self.currentSize = 0
首先，随便给我们一个list或者array，我们需要建堆，那么这个建堆有点像调整堆。所以这里我将建堆与调整堆，封装在一块！
【堆调整】
堆怎么调整呢？
一个最小堆满足完全二叉树性质！
最小堆满足的特点是：比左右子节点都小，并且当前节点位置如果为i，则左子节点为2i，右子节点为2i+1。
注意一点，这里写的是自顶向下的堆调整!
思路就是判断当前节点是否有子节点，如果没有不更新，有则更新。
更新操作：判断是否有右子节点，如果没有，则直接返回左自己点，随后比较当前节点与左子节点的大小即可，然后根据谁大谁小进行交换即可。
如果有右子节点，就比较麻烦了，得先判断是左子节点小，还是右子节点小，如果是左子节点，然后设定最小的节点，将当前节点与最小子节点比较，根据情况交换子节点与当前节点即可。
def updateHeap(self, i):
while (i * 2) <= self.currentSize:
# 堆调整
if i * 2 + 1 > self.currentSize:
j = i * 2
else:
if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
j = i * 2
else:
j = i * 2 + 1
if self.heapList[i] > self.heapList[j]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[j]
self.heapList[j] = tmp
i = j
【建堆】
从树中间开始，然后回溯到根节点，用updateHeap方法使得最大子节点下沉！
def heapify(self, alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.updateHeap(i)
i = i - 1
return self.heapList
【入堆出堆合并】
先把val加入到堆中，然后再remove掉堆顶元素，再生成新堆即可！
def heappushpop(self, val):
self.heapList.append(val)
self.currentSize += 1
print(self.heapList)
# 删除堆顶元素
self.heapList.remove(self.heapList[1])、
# 删除堆list前面的0元素
self.heapList.remove(self.heapList[0])
self.heapList = self.heapify(self.heapList)
self.currentSize -= 1
return self.heapList
【入堆】
这里主要是list操作，记得将开头的0号元素删除掉即可！
def heappush(self, val):
self.heapList.append(val)
self.currentSize += 1
self.heapList.remove(self.heapList[0])
self.heapList = self.heapify(self.heapList)
return self.heapList
【出堆】
直接出堆，0号元素是初始化的默认值，1号元素刚好是最小堆堆顶！
def heappop(self):
# self.heapify(self.heapList)
self.heapList.remove(self.heapList[1])
self.currentSize-=1
return self.heapList
4.回归
自虐模式完毕后，开始下一步的操作，那就是模仿上述实现本题。
上述的方法都是直接封装在这个类中，然后通过self调用！
思路1实现：
class KthLargest(object):
def __init__(self, k, nums):
self.heapList = [0]
self.currentSize = 0
self.k = k
l = nums[:k]
self.heapList = self.heapify(l)
for num in rest:
if num < self.heapList[1]:
continue
self.heapList=self.heappushpop(num)
def add(self, val):
if len(self.heapList)-1 < self.k:
self.heapList = self.heappush(val)
elif val > self.heapList[1]:
self.heapList=self.heappushpop(val)
return self.heapList[1]
思路2实现：
class KthLargest(object):
def __init__(self, k, nums):
self.heapList = [0]
self.currentSize = 0
self.k = k
self.heap = nums
self.heapList = self.heapify(self.heap)
while len(self.heapList)-1 > self.k:
self.heapList = self.heappop()
def add(self, val):
print(len(self.heapList))
if len(self.heapList)-1 < self.k:
self.heapList = self.heappush(val)
elif val > self.heapList[1]:
self.heapList=self.heappushpop(val)
return self.heapList[1]
参考文章: http://python.jobbole.com/85338/#article-comment
5.总结
对于这些数据结构，在考试的时候，笔试题万一考到，让你手写二叉树，堆排序实现，那在考场上直接写，有点伤，那么就得线下多多练习。
虽然这里实现了，但是遗憾的是提交到leetcode上超时，共10个用例，最后一个没通过，原因你懂的，超时了~~。下次用二叉排序实现一下。应该要好点。
一道简单的题，可以让你如醉如痴，更是因为这一道题，你才会学会很多，不要小看简单，简单中蕴含深意。