algorithm - 构建堆如何工作

Question

如果我有这个 A = [4 2 8 6 5 3] 并且我调用 BuildHeap(A)

BuildHeap(A){
 heap_length[A] ← length[A]
 for i ← floor(length[A]/2) downto 1 do
 Heapify(A, i)
}

它会像这样构建它

     4
  2     8
 6 5   3

或者像这样：

     8
  6     4
 2 5   3

Answer 1

如果你创建一个最小堆，

    2
  4   3
 6 5 8

如果你创建一个最大堆，

    8
  6   4
 2 5 3

请记住，最小堆总是在顶部有“最小”元素，而最大堆总是有“最大”。

创建堆的自下而上的过程是这样的：

要查看示例，请访问此处：http ://www.brpreiss.com/books/opus5/html/page502.html