关于二叉最小堆Priority Queue的push与pop算法追踪的疑问

首先得说一下，你现在画的树结构不对哦——这是个最大堆的结构，但我们要构建的是二叉最小堆，最小堆的核心性质是：每个父节点的值都小于等于它的子节点，根节点是整个堆里最小的元素。所以先从正确的堆构建过程开始梳理！

一、按顺序插入元素的Push过程追踪 #

我们依次插入5, 3, 9, 7, 2, 4, 6, 1, 8，结合你给出的push方法代码，每一步的堆变化如下（堆用数组存储，索引从1开始，array[0]是哨兵元素）：

1. 插入5 #

堆只有一个元素，数组：[null, 5]
树结构：

5

2. 插入3 #

3比父节点5小，触发上浮（percolate up）：

• hole初始为2，比较3和array[1]=5，3更小，把5移到位置2，hole变为1
• 现在hole=1，父节点是array[0]（哨兵元素3），循环停止，把3放到位置1
  数组：[null, 3, 5]
  树结构：

3
 /
5

3. 插入9 #

9比父节点3大，直接放到位置3
数组：[null, 3, 5, 9]
树结构：

3
 / \
5   9

4. 插入7 #

7的父节点是array[2]=5，7比5大，直接放到位置4
数组：[null, 3, 5, 9, 7]
树结构：

3
   / \
  5   9
 /
7

5. 插入2 #

2触发上浮：

• hole初始为5，比较2和array[2]=5，2更小，把5移到位置5，hole变为2
• 再比较2和array[1]=3，2更小，把3移到位置2，hole变为1
• 循环停止，把2放到位置1
  数组：[null, 2, 3, 9, 7, 5]
  树结构：

2
   / \
  3   9
 / \
7   5

6. 插入4 #

hole初始为6，父节点是位置3（6//2=3）的array[3]=9，4比9小，把9移到位置6，hole变为3；再比较4和array[1]=2，4更大，停止上浮，把4放到位置3
数组：[null, 2, 3, 4, 7, 5, 9]
树结构：

2
   / \
  3   4
 / \ /
7   5 9

7. 插入6 #

hole初始为7，父节点是位置3（7//2=3）的array[3]=4，6比4大，直接放到位置7
数组：[null, 2, 3, 4, 7, 5, 9, 6]
树结构：

2
     / \
    3   4
   / \ / \
  7   5 9 6

8. 插入1 #

1触发上浮：

• hole初始为8，父节点是位置4（8//2=4）的array[4]=7，1比7小，把7移到位置8，hole变为4
• 比较1和array[2]=3，1更小，把3移到位置4，hole变为2
• 比较1和array[1]=2，1更小，把2移到位置2，hole变为1
• 循环停止，把1放到位置1
  数组：[null, 1, 2, 4, 3, 5, 9, 6, 7]
  树结构：

1
     / \
    2   4
   / \ / \
  3   5 9 6
 /
7

9. 插入8 #

hole初始为9，父节点是位置4（9//2=4）的array[4]=3，8比3大，直接放到位置9
最终数组：[null, 1, 2, 4, 3, 5, 9, 6, 7, 8]
最终树结构：

1
     / \
    2   4
   / \ / \
  3   5 9 6
 / \
7   8

二、Pop操作的逻辑详解（结合你的Java代码） #

最小堆的pop()核心是取出根节点（最小元素），然后维持堆的性质，步骤如下：

1. 检查堆是否为空，为空则抛出NoSuchElementException；
2. 保存根节点元素（要返回的结果）；
3. 把堆的最后一个元素放到根节点位置，currentSize减1；
4. 执行下沉（percolate down）：从根节点开始，将当前元素与两个子节点比较，找到最小的子节点，如果当前元素比它大，就交换位置，重复这个过程直到当前元素小于等于子节点，或到达叶子节点。

模拟3次Pop操作 #

我们基于最终的堆数组[null,1,2,4,3,5,9,6,7,8]（currentSize=9）来模拟：

第一次Pop()

• 取出根元素1（第一个返回值）；
• 把最后一个元素8放到位置1，currentSize=8；
• 下沉8：
  • 子节点是array[2]=2和array[3]=4，最小是2，8>2，交换位置→array[1]=2，array[2]=8；
  • 现在hole=2，子节点是array[4]=3和array[5]=5，最小是3，8>3，交换→array[2]=3，array[4]=8；
  • hole=4，子节点是array[8]=7，8>7，交换→array[4]=7，array[8]=8；
  • hole=8是叶子节点，下沉结束。
• 堆数组变为：[null,2,3,4,7,5,9,6,8]

第二次Pop()

• 取出根元素2（第二个返回值）；
• 把最后一个元素8放到位置1，currentSize=7；
• 下沉8：
  • 子节点是array[2]=3和array[3]=4，最小是3，8>3，交换→array[1]=3，array[2]=8；
  • hole=2，子节点是array[4]=7和array[5]=5，最小是5，8>5，交换→array[2]=5，array[5]=8；
  • hole=5是叶子节点，下沉结束。
• 堆数组变为：[null,3,5,4,7,8,9,6]

第三次Pop()

• 取出根元素3（第三个返回值）；
• 把最后一个元素6放到位置1，currentSize=6；
• 下沉6：
  • 子节点是array[2]=5和array[3]=4，最小是4，6>4，交换→array[1]=4，array[3]=6；
  • hole=3，子节点是array[6]=9，6<9，停止下沉。
• 堆数组变为：[null,4,5,6,7,8,9]

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