python算法刷题——堆

菜鸡的刷题记录，基础知识不会写太多，有时间会写专题复习基础知识。第一轮刷题，所以解法代码可能都比较冗余/难看，主要是追求先有思路和会写。
更多优雅代码请参考解题区或评论区的大佬~

一、堆(heap)

堆，我们也称为优先级队列（priority queue） ，指的是没有父节点的值都大于（或小于）其子节点的完全二叉树。
python中默认实现的是最小堆。
python关于堆的实现有两个，一是heapq模块，另一个是PriorityQueue模块。

• heapq模块

import heapq
headp.heappush(heap, item)	# 将item加入heap中，保持堆的不变性
heapq.heappop(heap)	# 弹出并返回heap的最小元素。如果堆为空，抛出IndexError。heap[0]可以只访问最小元素而不弹出
heapq.heappushpop(heap, item)	# 将item放入heap中，然后弹出并返回heap最小元素。比先调用heappush()再调用heappop()效率高。
heapq.heapreplace(heap, item)	# 相当于先heappop()再heappush()，但效率较高
heapq.heapify(x)	# 将list x转换成堆，原地转换，O(n)

• PriorityQueue模块，底层其实也是heapq，所以时间复杂度上是一致的。PriorityQueue支持并发。

from queue import PriorityQueue
PriorityQueue.qsize()	# 返回队列大小
PriorityQueue.empty()	# 判断队列是否为空
PriorityQueue.full()	# 判断队列是否为满
PriorityQueue.put(item)	# 将item放入队列（维持优先队列顺序？)
PriorityQueue。get()	# 返回最小值（最小值最先被取出）

二、实战

1. leetcode215-数组中第K大的元素

思路： 要得到第k大的数，我们可以维护一个大小为k的最小堆，这样的话第k大的数就对应堆顶元素。
其他类似于求第k小的数也是一样的道理.

如何维护这个最小堆？

• 当最小堆内元素个数小于k时，新元素直接入堆；
• 否则当元素大于堆顶元素时，弹出堆顶元素并将新元素入堆；当元素小于堆顶元素时不操作。（这里因为是最小堆，所以新元素都必须保证比堆顶元素要小，如果新元素比堆顶元素大，就要替换掉堆顶元素）

import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        heap = []
        for i in range(k):
            heapq.heappush(heap, nums[i])
        for j in range(k, len(nums)):
            if not heap or heap[0] <= nums[j]:
                heapq.heapreplace(heap, nums[j])
        return heap[0]

2. leetcode295 数据流的中位数

思路： 我们可以想象将数据均分成两部分，分别放入最大堆和最小堆中（也就是说要保证最大堆元素和最小堆元素个数差值不超过1），并且维护最大堆的堆顶小于最小堆堆顶这一状态，那么中位数就是其中一个堆顶或两个堆顶的平均数。

那么如何将元素按照上述规则存入最大堆和最小堆中？

• 最大堆元素个数与最小堆相同时： 如果新元素大于最大堆堆顶 ，将其push进最小堆，反之则push进最大堆；（因为我们是始终要维护最大堆堆顶小于最小堆！！）
  
• 最大堆比最小堆多一个元素时： 如果新元素大于最大堆堆顶，将该元素push进最小堆，理由同上；如果新元素小于最大堆堆顶，那么需要先将最大堆的堆顶push进最小堆，再将新元素push到最大堆。（这个理解也容易，前面已经说了如果新元素大于最大堆堆顶应该要push进最大堆，那为什么要把原来的堆顶先pop呢，因为要维持两个堆元素个数相差不超过1的状态，那样才能将数据对半存储。）
• 最小堆比最大堆多一个元素时： 如果新元素小于最小堆堆顶，那么将元素push进最大堆；如果新元素大于最小堆堆顶时，先将最小堆堆顶push到最大堆，然后将新元素push到最小堆，原因与上面类似。

解决了元素如何存储的问题，那么中位数的取值也比较简单了：

• 当最大堆与最小堆元素个数相同时，取两个堆堆顶的平均值；
• 当最大堆多一个元素时，取最大堆堆顶；
• 当最小堆多一个元素时，取最小堆堆顶。

按照此思路实现如下，注意python中的heapq只实现了最小堆，所以采取取反的方式维护一个最大堆，麻烦在于每次取出或放入都要取反

import heapq
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min_heap = []
        self.max_heap = []     

    def addNum(self, num: int) -> None:
        len_min = len(self.min_heap)
        len_max = len(self.max_heap)
        """如果min_heap中还没有元素，直接加入"""
        if not self.min_heap:
            heapq.heappush(self.min_heap, num)
            
        """如果max_heap中还没有元素，注意不要直接加入，要判断新元素与min_heap元素的大小，因为要维持max_heap的堆顶元素小于min_heap的堆顶元素"""
        elif not self.max_heap:
            if num > self.min_heap[0]:
                heapq.heappush(self.max_heap, ~(self.min_heap[0]-1))
                self.min_heap[0] = num
            else: heapq.heappush(self.max_heap, ~(num-1))
            
        elif len_max == len_min:
            if num > ~(self.max_heap[0] - 1):
                heapq.heappush(self.min_heap, num)
            else:
                heapq.heappush(self.max_heap, ~(num - 1))
                
        elif len_max > len_min:
            if num > ~(self.max_heap[0] - 1):
                heapq.heappush(self.min_heap, num)
            else:
                heapq.heappush(self.min_heap, ~(self.max_heap[0] - 1))
                heapq.heapreplace(self.max_heap, ~(num - 1))
                
        elif len_max < len_min:
            if num < self.min_heap[0]:
                heapq.heappush(self.max_heap, ~(num - 1))
            else:
                heapq.heappush(self.max_heap, ~(self.min_heap[0] - 1))
                heapq.heapreplace(self.min_heap, num)

        

    def findMedian(self) -> float:
        len_min = len(self.min_heap)
        len_max = len(self.max_heap)
        if len_min == len_max: return (self.min_heap[0]+~(self.max_heap[0]-1))/2
        elif len_min > len_max: return self.min_heap[0]
        else: return ~(self.max_heap[0]-1)