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

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

代码：

template<class T> inline void MaxHeap<T>::make_heap(vector<T> & v) {
	if (heap_.size() != 0)
		heap_.clear();
	heap_ = v;

	// start with last parent, and reheapify_down back to root
	for (int i = parent(v.size() - 1); i >= 0; i--)
		reheapify_down(i);

	v = heap_;
}

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) 。

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

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

相关推荐