//@A: 需要检查的数组/堆
//@i: 以A[i]作为该函数检查的堆的根节点, 忽略A的其他部分
Max-Heapify(A, i)
l = LEFT(i) //求出左子节点
r = Right(i) //求出右子节点
if l <= A.heap-size and A[l]>A[i] //l<= A.heap-size to make sure left node exist inside the heap
largest = l
else largest = i
if r <= A.heap-size and A[r]>A[i]
largest = r
if largest != i
exchange A[i] with A[largest]
Max-Heapify(A, largest)
Build-Max-Heap(A)
A.heap-size = A.length
for i = floor(A.length/2) downto 1 //begin with the very last inside-node(nodes that are not on the leaf level.)
Max-Heapify(A, i)
//本质上是两步操作: 1, Build a heap; 2, Extract current-max-value, and re-Max-Heapify the rest;
Heap-Sort(A)
Build-Max-Heap(A)
for i = A.length downto 2
exchange A[1] with A[i] //将当前heap中最后一个node和根节点交换, 相当于输出当前Heap中的最大值;
A.heap-size--
Max-Heapify(A, 1) //把剩下元素中的最大值重新放到根节点上
时间复杂度分析
- 首先, Max-Heapify的时间复杂度是O(lgn), 这是因为其在堆中的每层操作都是O(1)级别的. 其最多可能会经过整棵树.
- 第一步, Build-Max-Heap(A)的时间复杂度为O(n)
T(n) = 层数* (每层节点数目每个节点消耗的时间) //note: 高度h是从下往上算, 底层高度h = 0;
= Σ<h=0~lgn> (ceil(n/2^(h+1)) * O(h))
= nΣ<h=0~lgn> (O(h/2^(h))) = O(n*2) = O(n);
//借助了Σ<k=0~无穷> (x^k) = 1/(1-x) (注: |x|<1) 和其的微分变种: Σ<k=0~无穷>k (x^k) = x/[(1-x)^2]
- 第二步, for循环中也有max-heapify的操作, 共n-1次, 因此时间复杂度也是n*logn
- 所以, 总体上看, Heap-sort的时间复杂度是nlgn;
