6.1 堆

伪代码 过程 PARENT(i)

//父节点的下标
PARENT(i)
return ⌊i/2⌋

伪代码 过程 LEFT(i)

//左孩子的下标
LEFT(i)
return 2i

伪代码 过程 RIGHT(i)

//右孩子的下标
RIGHT(i)
return 2i+1

6.2 维护堆的性质

伪代码 过程 MAX-HEAPIFY(A,i)

//维护最大堆性质的重要过程
//最大堆性质：A[PARENT(i)] ≥ A[i]
MAX-HEAPIFY(A,i)
  l = LEFT(i)
  r = RIGHT(i)
  if l ≤ A.heap-size and A[l] > A[i]
    largest = l
  else largest = i
  if r ≤ A.heap-size and A[r] > A[largest]
    largest = r
  if largest ≠ i
    exchange A[i] with A[largest]
    MAX-HEAPIFY(A,largest)

MAX-HEAPIFY的执行过程

6.3 建堆

伪代码 过程 BUILD-MAX-HEAPIFY(A,i)

//对树中的其他结点都调用一次MAX-HEAPIFY
BUILD-MAX-HEAPIFY(A,i)
  A.heap-size = A.length
  for i = ⌊A.length/2⌋ downto 1
     MAX-HEAPIFY(A,i)

例子

6.3-3

Solution

从6.1-7中，我我们知道堆的叶子是由 索引的节点。

因此，我们有

这意味着它适用于h。