leetcode295 一道题认识大顶堆和小顶堆
简单来说就是计算中位数。
这里采用大顶堆和小顶堆来分别存储中位数的两边。
1 堆排序
堆排序(Heap Sort)是利用堆这种数据结构所设计的一种排序算法。
堆：是一棵完全二叉树的结构，并且满足堆积的性质：每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。
堆排序先按从上到下、从左到右的顺序将待排序列表中的元素构造成一棵完全二叉树，然后对完全二叉树进行调整，使其满足:
堆积的性质：每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。
构建出堆后，将堆顶与堆尾进行交换，然后将堆尾从堆中取出来，取出来的数据就是最大(或最小)的数据。重复构建堆并将堆顶和堆尾进行交换，取出堆尾的数据，直到堆中的数据全部被取出，列表排序完成。
堆结构分为大顶堆和小顶堆：
-
大顶堆：每个节点(叶节点除外)的值都大于等于其子节点的值，根节点的值是所有节点中最大的，所以叫大顶堆，在堆排序算法中用于升序排列（因为尾部取出，从小的开始）。
-
小顶堆：每个节点(叶节点除外)的值都小于等于其子节点的值，根节点的值是所有节点中最小的，所以叫小顶堆，在堆排序算法中用于降序排列。
2 大顶/小顶堆创建和排序
python.heapq创建小顶堆
使用heapq库创建小顶堆。
创建函数有两个，heapq.heappush和heapq.heapify。前者逐个构建，后者一次性构建。
# coding=utf-8
import heapq
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
heapq.heappush(heap, num)
print("array:", array)
print("heap1: ", heap)
heapq.heapify(array)
print("heap2:", array)
得到：
array: [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap1: [5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50]
heap2: [5, 7, 21, 10, 17, 24, 27, 45, 15, 30, 36, 50]
heap1:
heap2:
堆排序
小顶堆
import heapq
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
heapq.heappush(heap, num)
print('heap[0]',heap[0])
print('first element',heapq.heappop(heap))
heap_sort = [heapq.heappop(heap) for _ in range(len(heap))]
print("heap sort result:", heap_sort)
运行
('heap[0]', 5) # 堆顶元素
('first element', 5) # 取出堆顶元素，会交换新的元素到堆顶
('heap sort result:', [7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]) # 依次取出堆顶，即升序排列
大顶堆
heapq库是实现小顶堆的方法，大顶堆只需要将所有的num以-num存入，在-heapq.heappop(heap)即可，如下。
代码：
import heapq
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
heapq.heappush(heap, -num)
print('heap[0]',-heap[0])
print('first element',-heapq.heappop(heap))
heap_sort = [-heapq.heappop(heap) for _ in range(len(heap))]
print("heap sort result:", heap_sort)
运行
('heap[0]', 50)
('first element', 50)
('heap sort result:', [45, 36, 30, 27, 24, 21, 17, 15, 10, 7, 5])
3 本题解法
```bash
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
左边使用大顶堆，存储较大的数字，右边使用小顶堆，存储较小的，然后看两边长度，相等的化，就取出两边的堆顶元素，作平均。不相等，就取出左边的堆顶元素。
from heapq import *
class MedianFinder:
def __init__(self):
self.A = [] # 小顶堆，保存较大的一半
self.B = [] # 大顶堆，保存较小的一半
def addNum(self, num: int) -> None:
if len(self.A) != len(self.B):
heappush(self.A, num)
heappush(self.B, -heappop(self.A))
else:
heappush(self.B, -num)
heappush(self.A, -heappop(self.B))
def findMedian(self) -> float:
return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0