8.1 Heap - swchen1234/Algorithm GitHub Wiki

理论

支持操作：

O(log N) Add
O(log N) Remove
O(1) Min or Max

Heap的实现

Heap 为统称，而heapq / PQ 为heap 的完美二叉树实现，用array实现，每个位置对应heap中的位置。??主要区别在于 heapq / PQ 的 remove 操作是 O(n) 的(From jiuzhang)??
heap的array实现，完全二叉树，第k个元素的父节点为k/2，左孩子为2k, 右孩子为2k+1
构建一个 heap 的时间复杂度？O(n) (python heapify)

常用技巧

Two heaps balancing 技巧；新元素总是加入h1，再从h1中到处一个元素加入h2, 这样可以保证维持heap的性质（h1总是小，h2总是大）
Lazy Removal， heap中存（val, index)， num[index]离开范围之后，不必马上pop出heap,仅仅pop出heap顶部的失效元素

Python library heapq Tips

若array中有初始值，一定要先heapify, 才能开始heapop, heapush
对于string, 因为heap只能实现min heap，故只能用来找最小的几个，若要找到最大的，可以使用heapq.nlargest来实现
若要customize heap，可以将元素放入class中

class Pair:
    def __init__(self, cnt, val):
        self.cnt = cnt
        self.val = val
    def __lt__(self, p):
        return self.cnt < p.cnt or (self.cnt == p.cnt and self.val > p.val)

应用

在一个变化的数组里，频繁找最大/最小
选出前k个（经常可以用quick select优化）
扫描线问题
heap中每pop出一个元素，将其邻居加入
Get Median(用2个heap)
Dijistra
其它

Problems

1. 在一个变化的数组里，频繁找最大/最小

2336. Smallest Number in Infinite Set用curr记录当前连续开始的第一个值+heap存之前add back回来的值，为了防止重复，用hashset记下heap中的值；popsmalest时，先pop出heap中最小值，若heap为空，返回curr, curr += 1
1405. Longest Happy StringmaxHeap中每次pop出最多的，若已经累计满两次，则pop出第二多的；也可以用greedy解，记录每个字母的剩余次数，以及连续次数
1792. Maximum Average Pass Ratioheap中存changeDiff, a, b
2182. Construct String With Repeat Limit 2263. Make Array Non-decreasing or Non-increasing遍历nums, 用heap存目前为止见到的最大数字，若出现比最大数小的数字，则res += maxV - num, 将heapq中最大数设为num.\

2. 选出前k个（经常可以用quick select优化）

215. Kth Largest Element in an ArrayminHeap实现，O（nlgk);若用quick select, O(n)
347. Top K Frequent Elementscounter+maxHeap/quick select
2542. Maximum Subsequence Score按照由大到小排列n1, n2组成的pair（以n2逆序排），n1的前k个组成heap，从n2[k-1]开始一直到n2[n-1]，固定n2[i]，从n1的heap中pop出最小的，加入n1[i]
857. Minimum Cost to Hire K Workers类似于2542，将wage/quality从小到大排列，理论上应该使wage/quality尽可能低（但所取的ratio不可能是前k-1个，这样的话，就找不到k个人)，在满足ratio大于所取raio的人中，找到min(k quality)，这可以通过heap实现 1509. Minimum Difference Between Largest and Smallest Value in Three Moves用heap实现partial sort，寻找最小的四个和最大的四个\

1337. The K Weakest Rows in a Matrix用二分法找到每行1的个数，再用min Heap找到solder最少的几行, O(mlogn+mlogk) 法二：vertical scan, 从最左边列开始从上至下，从左至右遍历，若所有全都遍历完，还没有满k个，从上至下，添加剩余行,O(mn),O(1)
2551. Put Marbles in Bags化为相邻两数和组成的数组，则问题即转化为找到最大/小的k-1个相邻两数和，可由minheap+maxheap实现，更进一步的，用quick select可达到O(n)的时间复杂度
2519. Count the Number of K-Big Indices从左至右遍历，用max heap维持最小的k个;右同\

3. 扫描线问题

253. Meeting Rooms II用heap比sort pairs更容易，pq模拟在开的会议，将meeting按开始时间排序，若start time<pq最早结束时间，增加房间；O（nlgn),时间复杂度同扫描线方法
1353. Maximum Number of Events That Can Be Attended遍历每一天，heap中存放已经开始但还没结束的活动，删除已经结束的活动，加入当天开始的活动；pop出最先结束的活动参加
2402. Meeting Rooms III用count array存每个房间的会议使用次数，且用heap 存放当前还没结束的活动都end time, 另外当有多个房间空时，需要assign最小房间号，所以还需要个heap来存放avaiable room id;遍历meetings(sort by endTime)，先清空heap1中<startTime的房间，加入heap2,若heap2非空，从heap2中pop出房间号；否则从heap1中pop出；返回count array中的最大值
218. The Skyline Problem将（point, height， start/end stutus)排序(先add再remove)后遍历，heap中存当前线上房屋高度
759. Employee Free Time用heap存每个人当前任务，并用curr记录当前所有任务最晚完成时间，pop出最先开始
1834. Single-Threaded CPU安装开始时间排序task，遍历，若currTime < task[i] 且heap中没有，则将currTime=task[i].time，2）将task中未进入queue且time<=currTime的都加入queue。3）从queue中找出下一个处理的任务
1882. Process Tasks Using Servers用两个数组，一个记录free server, 一个记录server in progress
1851. Minimum Interval to Include Each Queryquery, intervals分别排序,遍历query，将interval[0]<query pop出heapq, interval[1] > query pop出heaq，将堆顶放入答案\

4. heap中每pop出一个元素，将其邻居加入

23. Merge k Sorted Lists用heapq存放指向节点，但因为node不可比较,设listNode， ListNode.__lt__ = lambda x, y: x and y and x.val < y.val
632. Smallest Range Covering Elements from K Lists类似于23，用minHeap保持一个k-sized list,每个元素来自于一个数组，每次pop出最小，再补入其来自同一个list中的下一个，直至某个list结束，同时用max来记录heap中最大值，每次补入时更新max
373. Find K Pairs with Smallest Sums情侣配对题, 可以看成在一个二维递增矩阵中寻找前k大配对;从两队最小开始，放入max heap，每次去除放入邻居两个，用visited set防止重复 2462. Total Cost to Hire K Workers左右段都加入heap，记录左右端目前指针，heap中存（cost, index)
407. Trapping Rain Water II先将边框放入heap中，每次pop出最小值，加入邻居点；为了防止重负，用visited set来记录哪些点已被加入heap中
778. Swim in Rising Waterhp中存（maxwater, i, j)，每次pop出，将其邻居加入，直至遇到左下角\

5. Get Median

取sliding window median，=》 2 heaps。
经常用到rebalance + lazy removal

295. Find Median from Data Stream用maxHeap和minHeap，总是放入maxHeap，再pop出, 加入minHeap，若minHeap大于maxHeap， pop出minHeap，加入maxHeap
480. Sliding Window Median类似295，堆中存放(val, idx),但当i>k时，需要移除左端元素；当新加入的元素和需移除元素在同一个堆时，无需任何操作；否则需要re-balance；为了减少heap size，每次slide之后，需要将堆顶过期的元素移除掉
【难】1825. Finding MK Average用deque模拟data stream, 每次pop出最左边，借用480的lazy removal 方法，heap中存放（val, idx)，用四个heap, smallK(maxHeap), smallN_K(minHeap), bigK(minHeap), bigN_K(maxheap)\

6. Dijistra

见Data Structure: Dijistra 1631. Path With Minimum Effort用dist[n][m]存储到每个点的最小距离，若dist[i][j]被更新，将其加入heap中。\

7. 其它

minimum-area-rectangle

for each pair of rows, use hash map to store its largest columnidx so far.

1642. Furthest Building You Can Reach直观上，将大的落差近可能用梯子，小的落差用brick=》从左到右遍历，将变大的落差放入heap中，若size(heap)〉ladder#, 则pop出最小的几个落差用brick解决，直至brick超额\