【剑指offer】数据流中的中位数（最大最小堆实现）

╰半夏微凉° 2022-04-13 06:42 51阅读 0赞

**题目描述**  
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 3]

--------------------

构建一个最大堆和最小堆，并且保证最大堆中的数据都要小于最小堆的数据，也就是最大堆的根节点小于最小堆的根节点，插入的时候交替插入  
如果插入到最大堆：如果输入小于最大堆的根节点，插入到最大堆，如果大于最大堆的根节点，插入最小堆，将最小堆的根节点插入到左边的最大堆  
如果插入到最小堆：如果输入的大于最小堆的根节点，插入到最小堆，如果小于最小堆的根节点，那么插入最大堆，最大堆的根节点插入到右边的最小堆

import heapq
    class Solution:
        def __init__(self):
            self.maxHeap = []
            self.minHeap = []
            self.flag = 1
        def Insert(self, num):
            # write code here
            if self.flag:
                if self.minHeap == [] or num <= self.minHeap[0]: #插入最大堆
                    self.maxHeap.append(num) #插入
                    heapq.heapify(self.maxHeap) #调整
                elif num > self.minHeap[0]:  #大于最小堆最小元素，需要插入到最小堆，并且替换
                    self.maxHeap.append(heapq.heappop(self.minHeap))
                    heapq._heapify_max(self.maxHeap)
                    heapq.heappush(self.minHeap, num)
                self.flag = 0
            else:
                if self.maxHeap == [] or num >= self.maxHeap[0]:  #插入最小堆
                    heapq.heappush(self.minHeap, num)
                elif num < self.maxHeap[0]: #插入最大堆，并把最大堆的根替换到右边的最小堆
                    heapq.heappush(self.minHeap, heapq.heappop(self.maxHeap))  #最大堆的根
                    self.maxHeap.append(num)
                    heapq._heapify_max(self.maxHeap)
                self.flag = 1
        def GetMedian(self):
            # write code here
            if self.flag:
                return float('{:.2f}'.format((self.maxHeap[0] + self.minHeap[0]) / 2))
            else:
                return float('{:.2f}'.format(self.maxHeap[0]))

测试

sol = Solution()
    sol.Insert(5)
    sol.Insert(2)
    sol.Insert(6)
    sol.Insert(7)
    sol.Insert(8)
    print(sol.maxHeap)
    print(sol.minHeap)
    print(sol.GetMedian())

输出：

[6, 2, 5]
    [7, 8]
    6.0

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220413/447fb627e16844ca96498b814deb7c15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]: /images/20220413/73f1df4e2103417fa7745af5abbad0a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 2]: /images/20220413/c3ac7edc144d40d78d75ae3f2bd405b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 3]: /images/20220413/ab2b4e4358c4489bbccd9f704c62a4ad.png