筑堆的算法复杂度分析 O(n)

建堆的算法复杂度分析 O(n)

代码：

template<class T> inline void MaxHeap<T>::reheapify_down(int i) {if (heap_.empty())return;int current = i, max = i;int left = 1, right = 2;int size = heap_.size();do {current = max;left = left_child(current);right = right_child(current);if (left < size && heap_[left] > heap_[current])max = left;if (right < size && heap_[right] > heap_[max])max = right;if (max != current)swap(heap_[current], heap_[max]);} while (max != current);}

看似建堆(make_heap)的复杂度为O(nlogn)，实则为O(n)，reheapify_down不会touch到每个节点，所以不算简单的递归，只能算叠加。证明如下：

因为堆构建的是一颗平衡二叉树。于是有：

1. 一棵拥有n个节点的平衡二叉树，树高 h 约为 lg n 。

2. 树的第 i 层 最多有节点 2^i 个。注意，第 i 层的高度为 i + 1。如第0层的高度为1，拥有1个根节点。

那么做reheapify_down时，最底层(h-1)的节点不会动，倒数第二层（h-2）的节点最多往下移动一次，倒数第三层（h-3）的节点最多往下移动2次....第0层的节点往下最多移动（h-1）次。

所以，最坏情况下，每层所有节点都会往下移到最底层。

则，所有操作总和为     S = 2^(h-1)*0 + 2^(h-2)*1 + 2^(h-3) * 2 + ... + 2^1*(h-2) + 2^0*(h-1)        ----- （1）

把（1）式乘以2，再减去（1）式， 可得

S = 2^(h-1) + 2^(h-2) + ... + 2^1 - 2^0*(h-1)  = 2(1-2^(h-1))/(1-2) - (h-1) = 2^h - h- 1      ---- (2)

把h = lg n 代入 （2）式， 得 S = n - lgn - 1 <= n   (n >=1)

故而， 建堆复杂度为O(n) 。

水平有限，欢迎指正不对之处。

查看更多 下一篇