堆的构建方法：自底向上和自顶向下

# 1. 堆的基本概念和性质**

堆是一种完全二叉树，它满足以下性质：

- **形状性质：**堆是一棵完全二叉树，即除了最底层外，其他各层的节点数都达到最大值。
- **序性质：**对于任意一个节点及其左、右子节点，都有`key(node) >= key(left child)`和`key(node) >= key(right child)`。

# 2. 堆的构建方法

堆是一种完全二叉树，满足堆序性质：对于任意节点，其值都大于或等于其子节点的值。堆的构建方法主要有两种：自底向上的堆构建和自顶向下的堆构建。

### 2.1 自底向上的堆构建

自底向上的堆构建从树的叶节点开始，逐层向上构建堆。

#### 2.1.1 逐个插入法

逐个插入法将元素逐个插入到堆中，并调整堆以满足堆序性质。

def insert(heap, element):
    heap.append(element)
    i = len(heap) - 1
    while i > 1 and heap[i] > heap[i // 2]:
        heap[i], heap[i // 2] = heap[i // 2], heap[i]
        i //= 2

**代码逻辑逐行解读：**

1. 将元素添加到堆的末尾。
2. 设置当前元素索引 `i` 为堆的最后一个元素索引。
3. 循环比较当前元素 `heap[i]` 和其父节点 `heap[i // 2]` 的值。
4. 如果当前元素大于其父节点，则交换这两个元素。
5. 将 `i` 更新为其父节点的索引，继续比较和交换。
6. 循环直到 `i` 达到堆的根节点（`i == 1`）。

**参数说明：**

* `heap`: 待构建的堆
* `element`: 要插入的元素

#### 2.1.2 Floyd算法

Floyd算法是一种更有效率的逐个插入算法，它利用了堆的性质，将调整过程优化为 O(log n) 时间复杂度。

def floyd_insert(heap, element):
    heap.append(element)
    i = len(heap) - 1
    while i > 1:
        if heap[i] > heap[i // 2]:
            heap[i], heap[i // 2] = heap[i // 2], heap[i]
        else:
            break
        i //= 2

**代码逻辑逐行解读：**

1. 与逐个插入法类似，将元素添加到堆的末尾。
2. 循环比较当前元素 `heap[i]` 和其父节点 `heap[i // 2]` 的值。
3. 如果当前元素大于其父节点，则交换这两个元素。
4. 不同之处在于，如果当前元素小于或等于其父节点，则直接退出循环，因为此时堆序性质已满足。
5. 继续比较和交换，直到 `i` 达到堆的根节点（`i == 1`）。

**参数说明：**

* `heap`: 待构建的堆
* `element`: 要插入的元素

### 2.2 自顶向下的堆构建

自顶向下的堆构建从树的根节点开始，逐层向下调整堆。

#### 2.2.1 递归法

递归法使用递归函数从根节点开始向下调整堆。

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

**代码逻辑逐行解读：**

1. 获取当前节点 `i` 的左子节点 `left` 和右子节点 `right` 的索引。
2. 初始化最大值索引 `largest` 为当前节点索引 `i`。
3. 比较左子节点 `heap[left]` 和最大值 `heap[largest]` 的值，如果左子节点更大，则更新最大值索引 `largest`。
4. 比较右子节点 `heap[right]` 和最大值 `heap[largest]` 的值，如果右子节点更大，则更新最大值索引 `largest`。
5. 如果最大值索引 `largest` 不等于当前节点索引 `i`，则交换这两个节点的值。
6. 递归调用 `heapify_recursive` 函数对最大值节点的子节点进行调整。

**参数说明：**

* `heap`: 待构建的堆
* `i`: 当前