堆的调整方法：shift up 和 shift down

# 1. 向上调整

### 2.1.1 Shift Up 的基本原理

Shift Up 是堆调整的一种操作，用于将一个新元素插入堆中并保持堆的性质。其基本原理是：

- 将新元素插入堆的末尾。
- 比较新元素与其父节点的值。
- 如果新元素的值大于父节点，则交换新元素和父节点的位置。
- 重复上述步骤，直到新元素到达堆的正确位置。

### 2.1.2 Shift Up 的实现步骤

def shift_up(heap, i):
    """向上调整堆中索引为 i 的元素。

    Args:
        heap: 堆的列表表示。
        i: 要调整元素的索引。
    """
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

# 2. 堆的调整方法

堆的调整操作是维持堆性质的关键，分为向上调整（Shift Up）和向下调整（Shift Down）两种方式。

### 2.1 Shift Up：向上调整

#### 2.1.1 Shift Up 的基本原理

向上调整操作用于将一个新元素插入堆中时，将其向上移动到适当的位置，以满足堆的性质。具体而言，新元素会与它的父节点进行比较，如果新元素的值比父节点大（对于最大堆）或小（对于最小堆），则将新元素与父节点交换，并继续与父节点的父节点进行比较，直至新元素找到合适的位置。

#### 2.1.2 Shift Up 的实现步骤

def shift_up(heap, i):
    """向上调整堆中第 i 个元素。

    Args:
        heap: 堆列表。
        i: 要调整的元素的索引。
    """
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:  # 对于最大堆
            heap[i], heap[parent] = heap[parent], heap[i]
        i = parent

**逻辑分析：**

* `while i > 0`：循环直到到达堆的根节点。
* `parent = (i - 1) // 2`：计算父节点的索引。
* `if heap[i] > heap[parent]`：对于最大堆，比较新元素与父节点的值。如果新元素更大，则交换它们。
* `i = parent`：将当前索引更新为父节点的索引，继续向上比较。

### 2.2 Shift Down：向下调整

#### 2.2.1 Shift Down 的基本原理

向下调整操作用于删除堆顶元素后，将堆中最后一个元素移动到适当的位置，以满足堆的性质。具体而言，最后一个元素会与它的左右子节点进行比较，如果最后一个元素的值比子节点小（对于最大堆）或大（对于最小堆），则将最后一个元素与较大的子节点交换，并继续与较大的子节点的左右子节点进行比较，直至最后一个元素找到合适的位置。

#### 2.2.2 Shift Down 的实现步骤

def shift_down(heap, i, size):
    """向下调整堆中第 i 个元素。

    Args:
        heap: 堆列表。
        i: 要调整的元素的索引。
        size: 堆的大小。
    """
    while 2 * i + 1 < size:
        left = 2 * i + 1
        right = 2 * i + 2
        if right < size and heap[right] > heap[left]:  # 对于最大堆
            max_child = right
        else:
            max_child = left
        if heap[i] < heap[max_child]:
            heap[i], heap[max_child] = heap[max_child], heap[i]
        i = max_child

**逻辑分析：**

* `while 2 * i + 1 < size`：循环直到到达堆的最后一个节点。
* `left = 2 * i + 1`：计算左子节点的索引。
* `right = 2 * i + 2`：计算右子节点的索引。
* `if right < size and heap[right] > heap[left]`：对于最大堆，比较左右子节点的值。如果右子节点更大，则将 `max_child` 设置为右子节点的索引。
* `if heap[i] < heap[max_child]`：比较当前元素与 `max_child` 的值。如果当前元素更小，则交换它们。
* `i = max_child`：将当前索引更新为 `max_child` 的索引，继续向下比较。

# 3. 堆的构建

### 3.1 堆的构建方法

堆的构建方法主要有两种：直接构建法和堆化法。

#### 3.1.1 直接构建法

直接构建法是指从空堆开始，逐个插入元素，并对每个新插入的元素进行向上调整，直到堆满足堆的性质。

def build_heap_direct(arr):