1. 什么是大根堆？

大根堆是一种特殊的完全二叉树，其核心特性是：每个父节点的值大于或等于其左右子节点的值。这意味着堆的根节点（堆顶）始终是整个堆中的最大值，且插入、删除元素后可通过 “堆化” 操作快速恢复这一特性。

完全二叉树的结构特点（除最后一层外每层节点全满，最后一层节点从左到右连续排列），使其非常适合用数组存储 —— 这也是数组实现大根堆的核心优势。

2. 为什么用数组实现大根堆？

数组实现大根堆的核心依据是完全二叉树的下标特性：若数组 heap 存储堆元素，对于下标为 i 的节点：

• 左子节点下标 = 2*i + 1
• 右子节点下标 = 2*i + 2
• 父节点下标 = (i - 1) // 2

这种特性让我们无需额外存储指针（如树形节点的 left/right），仅通过下标计算就能快速定位父子节点，大幅降低了空间开销和操作复杂度。

3. 核心操作详解

基于数组的大根堆有两个核心操作：add（插入元素）和 pop（弹出堆顶元素），两者都依赖 “堆化” 过程维持大根堆性质。

（1）插入元素（add 方法）

插入元素的目标是：在维持完全二叉树结构的前提下，确保新元素插入后仍满足 “父≥子”。步骤：

1. 尾插：将新元素添加到数组末尾（对应完全二叉树的最后一个叶子节点）；
2. 向上堆化：从新元素开始，逐层与父节点比较。若新元素值更大，则交换两者，直到父节点值更大或到达根节点。

示例：插入 3 到堆 [8,7,5,4,6,1] 中：

• 尾插后数组为 [8,7,5,4,6,1,3]；
• 新元素 3 的父节点是 1（下标 2），3 > 1 → 交换得 [8,7,5,4,6,3,1]；
• 继续比较父节点 5（下标 2），3 < 5 → 停止堆化，最终堆为 [8,7,5,4,6,3,1]。

（2）弹出堆顶元素（pop 方法）

弹出堆顶（最大值）的目标是：删除最大值后，仍维持完全二叉树结构和 “父≥子” 规则。步骤：

1. 交换：将堆顶元素（下标 0）与数组末尾元素交换；
2. 删除：移除数组末尾元素（原堆顶）；
3. 向下堆化：从新堆顶（原末尾元素）开始，逐层与左右子节点中较大者比较。若父节点值更小，则交换两者，直到父节点值更大或到达叶子节点。

示例：弹出堆 [8,7,5,4,6,3,1] 的堆顶 8：

• 交换堆顶与末尾元素 → [1,7,5,4,6,3,8]；
• 删除末尾元素 → [1,7,5,4,6,3]；
• 向下堆化：新堆顶 1 与左右子节点 7（左）、5（右）比较，1 < 7 → 交换得 [7,1,5,4,6,3]；
• 继续比较 1 与左右子节点 4、6，1 < 6 → 交换得 [7,6,5,4,1,3]，此时满足大根堆规则。

4. 数组实现的优势

• 空间高效：无需存储指针，仅用数组下标计算父子关系，空间复杂度 O(n)（n 为元素数）；
• 操作高效：插入和弹出的堆化过程仅需遍历树高（O(log n)），远快于数组的 O(n) 操作；
• 实现简洁：核心逻辑依赖下标计算，代码量少，易于理解和维护。

5. 适用场景

基于数组的大根堆是实现优先队列的核心数据结构，广泛应用于：

• 任务调度（优先级高的任务先执行）；
• 堆排序（利用堆顶是最大值的特性排序）；
• Top K 问题（快速找到前 K 个最大值）。

6.代码

class BigHeap:
    """基于数组实现的大根堆
    
    大根堆是满足"父节点值 ≥ 左右子节点值"的完全二叉树，本实现通过数组存储元素，
    利用完全二叉树的下标特性快速定位父子节点，支持高效的插入和弹出操作。
    """
    def __init__(self):
        self.heap = []  # 用数组存储堆元素，下标对应完全二叉树的节点编号
        self.size = 0   # 堆中元素的实际数量（避免频繁调用len(heap)）


    def __len__(self):
        """支持用len(heap)获取堆大小，符合Python容器规范"""
        return self.size


    def add(self, val):
        """向堆中插入元素，并通过向上堆化维持大根堆性质
        
        步骤：
        1. 将新元素添加到数组末尾（对应完全二叉树的最后一个叶子节点）
        2. 向上堆化：从新元素开始，逐层与父节点比较，若子节点值更大则交换，
           直到父节点值更大或到达根节点（保证父≥子）
        """
        # 1. 新元素插入数组末尾
        self.heap.append(val)
        # 记录新元素的初始下标（当前堆大小即为新元素的索引）
        current_idx = self.size
        # 更新堆大小
        self.size += 1

        # 2. 向上堆化
        while current_idx > 0:  # 未到达根节点（根节点下标为0）
            # 计算父节点下标：完全二叉树中，子节点i的父节点为 (i-1)//2
            parent_idx = (current_idx - 1) // 2
            # 若子节点值 > 父节点值，违反大根堆规则，交换两者
            if self.heap[current_idx] > self.heap[parent_idx]:
                self.heap[current_idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[current_idx]
                # 继续向上比较父节点的父节点
                current_idx = parent_idx
            else:
                # 父节点值更大，已满足大根堆规则，停止堆化
                break


    def pop(self):
        """弹出堆顶元素（最大值），并通过向下堆化维持大根堆性质
        
        步骤：
        1. 交换堆顶（下标0）与数组末尾元素（最后一个叶子节点）
        2. 删除数组末尾元素（原堆顶，已被交换到末尾）
        3. 向下堆化：从新堆顶开始，逐层与左右子节点中较大者比较，
           若父节点值更小则交换，直到父节点值更大或到达叶子节点
        """
        if self.size == 0:
            raise Exception('empty heap!')  # 边界处理：堆为空时无法弹出

        # 1. 交换堆顶与末尾元素（保证删除后仍为完全二叉树）
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        # 2. 删除末尾元素（原堆顶，此时已被交换到最后）
        self.heap.pop()
        # 更新堆大小
        self.size -= 1

        # 3. 向下堆化：从新堆顶（原末尾元素）开始调整
        current_idx = 0
        while True:
            # 计算左右子节点下标：左子节点 = 2*i + 1，右子节点 = 2*i + 2
            left_idx = 2 * current_idx + 1
            right_idx = 2 * current_idx + 2

            # 情况1：当前节点无左子节点（已是叶子节点），无需继续调整
            if left_idx >= self.size:
                break

            # 情况2：只有左子节点（无右子节点）
            elif right_idx >= self.size:
                # 若父节点值 < 左子节点值，交换并继续向下调整
                if self.heap[current_idx] < self.heap[left_idx]:
                    self.heap[current_idx], self.heap[left_idx] = self.heap[left_idx], self.heap[current_idx]
                    current_idx = left_idx
                else:
                    # 父节点值更大，满足规则，停止调整
                    break

            # 情况3：同时有左右子节点
            else:
                # 若父节点值 ≥ 左右子节点，满足大根堆规则，停止调整
                if self.heap[current_idx] >= self.heap[left_idx] and self.heap[current_idx] >= self.heap[right_idx]:
                    break
                # 否则，与左右子节点中较大的一个交换（保证父节点始终是最大值）
                elif self.heap[left_idx] > self.heap[right_idx]:
                    self.heap[current_idx], self.heap[left_idx] = self.heap[left_idx], self.heap[current_idx]
                    current_idx = left_idx  # 继续调整左子树
                else:
                    self.heap[current_idx], self.heap[right_idx] = self.heap[right_idx], self.heap[current_idx]
                    current_idx = right_idx  # 继续调整右子树


# 测试代码
if __name__ == '__main__':
    heap = BigHeap()
    # 插入测试数据
    l = [5, 4, 8, 7, 6, 1, 3]
    for val in l:
        heap.add(val)
    print("插入后堆的结构：", heap.heap)  # 输出：[8, 7, 5, 4, 6, 1, 3]（大根堆，堆顶为8）
    print("堆的大小：", len(heap))        # 输出：7

    # 弹出堆顶（最大值8）
    heap.pop()
    print("弹出堆顶后堆的结构：", heap.heap)  # 输出：[7, 6, 5, 4, 3, 1]（新堆顶为7）
    print("堆的大小：", len(heap))          # 输出：6