# 第四天(堆)(贪心)

**今天完成题目：** 1045， 1577，703\
1046： 最后一块石头

* a,b=b,a可以快速实现交换
* 使用heapq包来实现堆，但是里面默认只有最小堆
* 也可以使用内置的隐藏函数实现最大堆，速度快但耗内存
* heapq的最大堆没有实现插入后调整的函数

1577：找出最小的n个数

* 继续使用heapq包实现，调用heapq.nsmallest(n, arr)实现，但是速度貌似还能改进

703：数据流中的第k个大的数

* 注意，不一定要用大顶堆，然后找出第k个大
* 使用小顶堆，切割出最大的k个值，之后顶部就是第k个大的值了

heapq包的使用

1. heapq.heapify可以原地把一个list调整成堆\[小顶堆] 而 heapq.nlargest 会调成大顶堆
2. heapq.heappop可以弹出堆顶，并重新调整
3. heapq.heappush可以新增元素到堆中，不会调整
4. heapq.heapreplace可以替换堆顶元素，并调整下
5. 为了维持为K的大小，初始化的时候可能需要删减，后面需要做处理就是如果不满K个就新增，否则做替换；
6. heapq其实是对一个list做原地的处理，第一个元素就是最小的，直接返回就是最小的值

**贪心算法完成题目：** 1221 ，1518 1221：分割平衡字符串

* 没有看清题意，错误理解了平衡字符串一定要对称，写错了
* 后面才发现平衡字符串是指包含的字母数量相同即可，通过balance变量，进行增减，为0时便是一个平衡子串

1518：换酒问题

* 简单，通过整除//和求模%循环一下就出来了，记得理清思路
