堆的应用之六：数据流中位数问题

# 1.1 堆的基本概念

堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值。这种数据结构具有两个重要的性质：

- **堆序性：**每个节点的值都大于或等于其子节点的值。
- **完全二叉树：**除了最后一层之外，每一层都完全填充，最后一层尽可能地从左向右填充。

# 2. 堆的算法实现

堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值。堆有两种类型：最大堆和最小堆。最大堆中，根节点的值最大，而最小堆中，根节点的值最小。

### 2.1 堆的初始化和插入

堆的初始化可以通过一次性插入所有元素或逐个插入元素来实现。

#### 一次性插入

def build_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, i, n)

参数说明：
- arr：待构建的堆
- i：从堆的最后一个非叶子节点开始，逐层向上调整
- n：堆的大小

逻辑分析：
从最后一个非叶子节点开始，逐层向上调整，确保每个子树都是堆。

#### 逐个插入

def insert_heap(heap, value):
    heap.append(value)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent

参数说明：
- heap：待插入元素的堆
- value：待插入的元素

逻辑分析：
将元素插入堆的末尾，然后从该元素开始，逐层向上调整，确保堆的性质。

### 2.2 堆的删除和调整

#### 删除根节点

def delete_root(heap):
    if len(heap) == 0:
        return None
    root = heap[0]
    heap[0] = heap.pop()
    heapify(heap, 0, len(heap))
    return root

参数说明：
- heap：待删除根节点的堆

逻辑分析：
将根节点与最后一个元素交换，然后从根节点开始，逐层向下调整，确保堆的性质。

#### 调整堆

def heapify(heap, i, n):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    if left < n and heap[left] > heap[i]:
        largest = left
    if right < n and heap[right] > heap[largest]:
        largest = right
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        heapify(heap, largest, n)

参数说明：
- heap：待调整的堆
- i：待调整的节点索引
- n：堆的大小

逻辑分析：
比较当前节点与左右子节点，找出最大值，如果最大值不是当前节点，则交换当前节点与最大值，并递归调整最大值所在子树。

### 2.3 堆排序算法

堆排序是一种基于堆的数据排序算法。其基本思想是：

1. 将待排序的数组构建成一个最大堆。
2. 将根节点与最后一个元素交换，然后调整堆，使根节点变为最大值。
3. 重复步骤 2，直到堆中只剩下一个元素。

def heap_sort(arr):
    build_heap(arr)
    for i in range(len(arr) - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, 0, i)

参数说明：
- arr：待排序的数组

逻辑分析：
先将数组构建成堆，然后逐个将根节点与最后一个元素交换，并调整堆，最终得到一个从小到大排序的数组。

# 3.1 数据流中位数问题

#### 3.1.1