以下的最小堆顺序

Question

考虑通过向空堆中重复插入值而构建的最小堆 [13, 24, 32, 32, 41, 38, 50, 48, 40]。假设最后插入的值是 24。插入该值之前的堆结构是什么？

我不知道这个问题的答案是什么

Answer 1

为了解决这个问题，它有助于制作树的视觉表示：

         _ 13 _
        /      \
      24        32
     /  \      /  \
   32    41  38    50
  /  \
48    40

由于 24 被插入到当前被 40 （数组中的最后一个条目）占据的位置，我们知道这个 20 在树上冒泡的路径（即通过 32），我们可以做相反的事情：

         _ 13 _
        /      \
      32        32
     /↙ \      /  \
   40    41  38    50
  / ↘\
48    24

最后，我们反转 24 的初始插入：

         _ 13 _
        /      \
      32        32
     /  \      /  \
   40    41  38    50
  /
48 

将其写回数组形式：

[13,32,32,40,41,38,50,48]