1. 什么是大根堆？

大根堆是一种特殊的完全二叉树，满足 “每个父节点的值大于或等于其左右子节点的值”。其核心特性是：根节点始终为整个堆的最大值，且插入、删除操作可通过 “堆化” 快速维持结构特性。

2. 为什么用树节点实现？

通常堆采用数组实现（利用完全二叉树的下标特性），但树形实现更直观地体现堆的逻辑结构：

• 每个节点通过left和right引用明确关联子节点，清晰展示 “父子关系”；
• 插入和堆化过程可通过节点引用直接操作，便于理解堆的动态调整机制。

3. 核心实现思路

（1）节点结构

用TreeNode类存储值及子节点引用，每个节点包含val（值）、left（左子节点）、right（右子节点）。

（2）插入操作（add方法）

1. 定位插入位置：完全二叉树的新节点需插入到 “最后一个叶子节点的下一位”，通过堆大小size的二进制位确定路径（例如size=5的二进制101对应 “根→右→左”）。
2. 向上堆化：新节点插入后，若其值大于父节点，交换两者值并逐层向上调整，直至满足 “父≥子”。

（3）弹出堆顶操作（pop方法）

1. 替换堆顶：用最后一个叶子节点的值覆盖根节点（堆顶），并删除最后一个节点（维持完全二叉树结构）。
2. 向下堆化：从根节点开始，与左右子节点中较大者比较，若父节点值更小则交换，逐层向下调整，直至满足 “父≥子”。

4. 优缺点分析

• 优点：逻辑直观，直接体现堆的树形结构，便于理解堆化过程；
• 缺点：相比数组实现，需维护节点引用，操作效率略低（额外的指针访问开销）。

5.代码

from queue import deque

class TreeNode:
    """二叉树节点类，存储堆的元素值及左右子节点引用"""
    def __init__(self, val=None, left=None, right=None):
        self.val = val  # 节点值
        self.left = left  # 左子节点
        self.right = right  # 右子节点


class BigHeap:
    """基于树节点实现的大根堆
    
    大根堆是满足"父节点值 ≥ 左右子节点值"的完全二叉树，本实现通过显式的二叉树节点
    构建堆结构，支持插入、弹出堆顶、层次遍历等操作，直观体现堆的树形逻辑。
    """
    def __init__(self, root_val=0):
        """初始化大根堆，根节点默认值为0"""
        self.root = TreeNode(root_val)  # 堆的根节点（始终为最大值）
        self.size = 1  # 堆中节点总数（初始包含根节点）


    @property
    def height(self):
        """计算堆的高度（完全二叉树的深度）"""
        h = 0
        node = self.root
        while node.left:  # 沿左子树遍历至最深层
            h += 1
            node = node.left
        return h


    def bfs(self):
        """层次遍历堆，按层输出节点值（用于可视化堆结构）"""
        if not self.root:
            return []
        queue = deque([self.root])
        result = []
        while queue:
            level_size = len(queue)
            current_level = []
            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(current_level)
        return result


    def add(self, val):
        """插入元素并维持大根堆性质
        
        步骤：1. 定位新节点插入位置（完全二叉树最后一个叶子）
              2. 插入新节点
              3. 向上堆化（与父节点比较交换，确保父≥子）
        """
        # 创建新节点，更新堆大小
        new_node = TreeNode(val)
        self.size += 1

        # 定位新节点的父节点（基于完全二叉树的二进制路径）
        i = self.size.bit_length() - 2  # 路径层数
        path = [self.root]  # 记录从根到父节点的路径
        current_node = self.root

        while i > 0:
            if self.size & (1 << i):  # 二进制位为1→右子树
                current_node = current_node.right
            else:  # 二进制位为0→左子树
                current_node = current_node.left
            path.append(current_node)
            i -= 1

        # 插入新节点到父节点的左/右子树
        if self.size & 1:
            current_node.right = new_node
        else:
            current_node.left = new_node
        path.append(new_node)

        # 向上堆化：确保父节点值≥子节点值
        for i in range(len(path)-1, 0, -1):
            child = path[i]
            parent = path[i-1]
            if child.val > parent.val:
                child.val, parent.val = parent.val, child.val  # 交换值
            else:
                break  # 满足大根堆规则，停止堆化


    def pop(self):
        """弹出堆顶元素（最大值）并维持大根堆性质
        
        步骤：1. 定位最后一个叶子节点
              2. 用最后一个节点值替换堆顶
              3. 删除最后一个节点
              4. 向下堆化（与子节点比较交换，确保父≥子）
        """
        if self.size == 0:
            raise IndexError("堆为空，无法弹出元素")

        # 定位最后一个叶子节点的父节点
        last_parent = self.root
        i = self.size.bit_length() - 2
        while i > 0:
            if self.size & (1 << i):
                last_parent = last_parent.right
            else:
                last_parent = last_parent.left
            i -= 1

        # 用最后一个节点值替换堆顶，并删除最后一个节点
        if self.size & 1:
            self.root.val = last_parent.right.val
            last_parent.right = None
        else:
            self.root.val = last_parent.left.val
            last_parent.left = None

        # 向下堆化：从根节点开始调整
        current = self.root
        while True:
            # 叶子节点，无需调整
            if not current.left and not current.right:
                break

            # 只有左子节点
            if not current.right:
                if current.val < current.left.val:
                    current.val, current.left.val = current.left.val, current.val
                    current = current.left
                else:
                    break

            # 只有右子节点（完全二叉树中理论不存在，仅作兼容）
            elif not current.left:
                if current.val < current.right.val:
                    current.val, current.right.val = current.right.val, current.val
                    current = current.right
                else:
                    break

            # 既有左右子节点，与较大子节点交换
            else:
                if current.val >= current.left.val and current.val >= current.right.val:
                    break
                if current.left.val > current.right.val:
                    current.val, current.left.val = current.left.val, current.val
                    current = current.left
                else:
                    current.val, current.right.val = current.right.val, current.val
                    current = current.right

        self.size -= 1


# 测试代码
if __name__ == "__main__":
    heap = BigHeap(root_val=0)
    # 插入元素
    for val in [1, 8, 6, 5, 3, 10, 2]:
        heap.add(val)
    print("插入后堆的层次结构：", heap.bfs())  # 输出：[[10], [6, 8], [2, 5, 1, 3], [0]]
 
    # 弹出堆顶（10）
    heap.pop()
    print("弹出堆顶后层次结构：", heap.bfs())  # 输出：[[8], [6, 3], [2, 5, 1, 0]]