← 演示目录

建堆与下滤

全书 10

CLRS 例:1 下标数组 [4,1,3,2,16,9,10,14,8,7],大顶堆。自底向上从 ⌊n/2⌋=5 建到 1。左子 2i(当 2i≤n),右子 2i+1(当 2i+1≤n)。建堆 O(n),不是 O(n log n)。堆排通常不稳。下滤模式从已建成堆做一次 extract-max。

STEP 0
READY从 i=5 往根建。