# 如醉如痴之最小堆

0.说在前面1.问题2.思考3.自虐4.回归5.总结6.作者的话

### 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 `k`and 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.

### 2.思考

```heapq.heappush(heap, item) 把item添加到heap中（heap是一个列表）
heapq.heappop(heap) 删除堆顶元素，返回删除后的堆
heapq.heappushpop(heap, item) 先把item加入到堆中，然后再pop，比heappush()再heappop()要快得多
heapq.heapify(x) 将列表x进行堆调整，默认的是小顶堆
```

```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]
```

```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.自虐

```updateHeap()  # 调整堆
heapify()     # 创建堆同时调整堆
heappushpop() # 先把item加入到堆中，然后再pop，在调整堆
heappop()     # 删除堆顶元素，返回删除后的堆
```

```def __init__(self):
self.heapList = [0]
self.currentSize = 0
```

```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
```

```    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
```

```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
```

```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
```

```def heappop(self):
# self.heapify(self.heapList)
self.heapList.remove(self.heapList[1])
self.currentSize-=1
return self.heapList
```

### 4.回归

```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]
```

```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]
```

0 条评论

• ### 1.8亿条海量Txt数据存储MySQL实践

最近出去旅游了，嗨皮了嗨皮，明天上班，开始做作业，今日将1.8亿数据存储的方式进行总结，欢迎大家拍砖！

• ### 揭开神秘的面纱

打开f12检查页面后，刷新一下页面，点击Network，再点击下面的XHR，查看动态数据，会发现如下图所示，有两行数据。

• ### 第二期编程实践之快乐数

0.导语1.快乐数1.0 问题1.1 递归+哈希+循环1.2 非递归+哈希+循环1.3 循环替代1.4 哈希表替代1.5 数字4的作用2.作者的话

• ### Python面向对象(成员)(二)

特点: 在声明的时候. 需要给出self, self必须放在第一个位置

• ### 利用Python编写一个行业专用的小计算器

前言：本文讲述的是如何利用python编程制作一个适用于指定行业的计算器，方便计算结果，涵盖的知识点由Python编写GUI界面程序，利用爬虫采集实时的汇率数据...

• ### PyQt 编程入门（六.3）

from PyQt5.QtCore import QTimer from PyQt5.QtWidgets import * import sys

• ### python的tkinter编程（八）Entry组件的详细介绍，以登录界面作为讲解

写一个按钮，绑定一个方法，当点击这个按钮的时候，就会执行这个方法，在这个方法里面 获取到对应的你输入的值，将获取到的值传到数据库里面进行比对，失败给一个返回的...

• ### PyQt5 非模态对话框(live 型)

本篇介绍非模态“实时”（live）对话框。与上一篇讲的”apply型“非模态对话框的区别是，非模态“实时”（live）对话框没有任何按钮，且所做的任何改变会自动...

• ### PyQt5 对话框 数据验证

本篇介绍PyQt5对话框的数据合法性的验证。有两种验证方式：预防式验证（preventative）和 提交后验证 (post-mortem)。预防式验证适合于单...