【堆与优先队列应用课】：堆结构的算法魔术揭秘

# 1. 堆结构的理论基础

## 堆的定义和特性
堆是一种特殊的完全二叉树，通常利用数组来实现。它允许任何一个节点的值都满足“父节点的值总是大于（或小于）其子节点的值”的特性，从而保证了堆的有序性。基于这样的特性，堆可以分为最大堆和最小堆，分别用于实现优先级队列。

## 完全二叉树与二叉堆的关系
完全二叉树是一种特殊的二叉树，其特点是除了最后一层外，其他各层的节点数都是满的，而最后一层的节点都集中在左侧。二叉堆是一种基于完全二叉树的堆结构，能够用数组表示，从而实现高效的动态数据集合管理。由于这种表示方式，二叉堆支持快速的堆化操作，如上浮和下沉，这为优先级队列提供了基础。

## 堆操作的基本原理：插入和删除
堆的基本操作包括插入和删除。插入操作是将一个元素加入堆中，并通过上浮操作保持堆的有序性；而删除操作通常是移除堆顶元素，然后将堆的最后一个元素放到堆顶，通过下沉操作重新调整堆。这些操作保证了堆的结构特性，也是优先级队列实现的基础。

# 假设这是最小堆的实现

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, index):
        return (index - 1) // 2

    def insert(self, key):
        self.heap.append(key)
        index = len(self.heap) - 1
        while index != 0 and self.heap[self.parent(index)] > self.heap[index]:
            self.heap[index], self.heap[self.parent(index)] = self.heap[self.parent(index)], self.heap[index]
            index = self.parent(index)

    def extract_min(self):
        if len(self.heap) <= 0:
            return None
        elif len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.heapify(0)
        return root

    def heapify(self, index):
        smallest = index
        left = 2 * index + 1
        right = 2 * index + 2

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right

        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self.heapify(smallest)

在上述示例中，我们定义了一个最小堆的类`MinHeap`，其中包含了插入`insert`和删除最小值`extract_min`的基本操作。插入操作是通过上浮（`heapify`函数从下往上）实现的，而删除最小值操作则是通过下沉（`heapify`函数从上往下）来实现。这保证了我们的堆始终保持最小堆的性质。

# 2. 堆的内部实现机制

## 2.1 堆的数组表示

### 2.1.1 数组与堆节点的映射关系

堆在内存中的存储通常使用数组来完成。数组中的元素按照堆序性质排列，即任何一个父节点的值都必须大于或等于其子节点的值。这种性质使得堆的表示异常简洁，且便于通过数组索引来快速访问堆中的任意节点。

在数组中，对于任意一个位于索引`i`的节点，其子节点的索引分别为`2*i + 1`和`2*i + 2`（如果存在的话），其父节点的索引为`(i - 1) / 2`。这个映射关系是堆操作能够快速执行的根基。以下是具体映射关系的代码实现：

def get_left_child(index, heap_size):
    """返回索引为index的节点的左子节点索引"""
    return 2 * index + 1 if 2 * index + 1 < heap_size else None

def get_right_child(index, heap_size):
    """返回索引为index的节点的右子节点索引"""
    return 2 * index + 2 if 2 * index + 2 < heap_size else None

def get_parent(index):
    """返回索引为index的节点的父节点索引"""
    return (index - 1) // 2

# 示例数组表示的堆结构
heap_array = [5, 7, 9, 1, 3] # 二叉堆数组表示

### 2.1.2 堆序性质的数学证明

堆序性质的数学证明基于归纳法。我们可以定义一个基础情况（通常是一棵只有根节点的树），然后假设对于一个具有`k`个节点的堆，堆序性质是成立的。接着我们证明当我们在堆中添加一个新的节点并重新调整后，堆序性质依然保持。

添加新节点通常意味着在堆的底部添加一个元素，然后执行上浮（或称作提升）操作，通过交换节点，直到新节点满足堆序性质。这个过程确保了新节点会与较小的父节点交换，保证了每个父节点的值都不小于其子节点的值。

### 2.2 堆的调整过程

#### 2.2.1 上浮与下沉操作原理

上浮（或提升）操作是将一个新插入的节点与它的父节点比较，如果节点的值大于父节点的值，则交换它们的位置。这个过程一直重复，直到节点的值不再大于父节点的值为止。上浮操作保证了堆序性质中父节点总是大于其子节点的要求。

下沉（或下沉）操作则是执行相反的操作。当我们从堆中移除最大的元素（即堆顶元素）后，我们用堆的最后一个元素填充这个空位，然后执行下沉操作，将这个新的堆顶元素与它的子节点比较，并与较大的子节点交换位置。这个过程会一直进行，直到新的堆顶元素大于或等于其子节点为止。下沉操作确保了移除最大元素后，剩余部分依然保持堆序性质。

def sift_up(index, heap):
    """上浮操作""