能否不使用数组、链表等额外结构，仅通过TreeNode实现binary heap？

首先明确结论：可以实现，仅需要额外维护两个基础变量：堆的总节点数size、根节点root，不需要依赖数组、外置链表存储节点，提到的两个核心实现问题都可以通过完全二叉树的序号二进制规律解决。

插入新节点时维持完全二叉树结构的方案 #

完全二叉树的节点按层序编号后，编号的二进制特征可以直接用来定位插入位置，无需遍历整棵树或者依赖数组：

• 根节点编号为1，任意节点的左孩子编号为父节点编号 * 2，右孩子编号为父节点编号 * 2 + 1
• 新插入节点的编号为size + 1，将该编号转为二进制后去掉最高位的1，剩余每一位对应从根节点出发的遍历路径：0代表走左子节点，1代表走右子节点，遍历结束的位置就是新节点的父节点，将新节点挂到对应空的左/右位即可。

插入后上浮调整的逻辑非常简单：通过节点的parent指针，不断将新节点和父节点比较值的大小，不符合堆性质就交换两个节点的值，直到到达根节点或者满足堆性质为止。

插入操作伪代码示例 #

function insert(value):
    new_node = TreeNode(value)
    if size == 0:
        root = new_node
        size = 1
        return
    # 计算新节点编号，获取路径
    path = binary(size + 1).substring(1) # 去掉最高位的1
    current = root
    for i in 0 to len(path) - 2: # 最后一位是新节点的左右标识，前面的是父节点路径
        if path[i] == '0':
            current = current.left
        else:
            current = current.right
    # 挂新节点
    new_node.parent = current
    if path[-1] == '0':
        current.left = new_node
    else:
        current.right = new_node
    size += 1
    # 上浮调整
    bubble_up(new_node)

取出根节点后的重新堆化方案 #

取根节点后的核心操作是用最后一个节点替换根节点，再执行下沉调整，最后一个节点同样可以通过size的二进制特征快速定位：

1. 用size的值转二进制后去掉最高位，按上述路径规则遍历，得到最后一个节点
2. 将最后一个节点的值赋值给根节点，然后删除最后一个节点（父节点对应左/右指针置空），size减1
3. 从根节点开始执行下沉调整：每次将当前节点和左右子节点比较，选择优先级最高的节点交换值，直到当前节点是叶子节点或者满足堆性质为止。

弹出根节点操作伪代码示例 #

function pop_root():
    if size == 0:
        return null
    res = root.value
    if size == 1:
        root = null
        size = 0
        return res
    # 找最后一个节点
    path = binary(size).substring(1)
    current = root
    parent = null
    for bit in path:
        parent = current
        if bit == '0':
            current = current.left
        else:
            current = current.right
    # 替换根值，删除最后节点
    root.value = current.value
    if path[-1] == '0':
        parent.left = null
    else:
        parent.right = null
    size -= 1
    # 下沉调整
    bubble_down(root)
    return res

该方案仅依赖TreeNode的left/right/parent属性、两个普通变量size和root，没有用到任何数组、链表结构，时间复杂度和数组实现的二叉堆完全一致，插入和弹出的时间复杂度都是O(log n)。

内容的提问来源于stack exchange，提问作者curious_birdie