首页 > 代码库 > 堆

堆是完全二叉树,一个大小为n的堆为一棵包含n个节点的完全二叉树。完全二叉树的根称为堆顶。当堆中每个节点的关键字值大于等于其双亲节点的关键字值,这样的堆称为最小堆,当子节点的值都小于等于其父节点时,称为最大堆。

使用数组来保存堆中元素。对于数组中的i节点,其子节点为 2i +1 和2i + 2。则由此可以轻松的判断节点之间的关系。然后我们考虑最小堆的具体情况。

然后考虑堆的向下调整运算AdjustDown(T heap[],int r,int j)。在堆中r+1 到 j 之间的元素都已满足最小堆的要求,然后加入元素r即heap[r],调整顺序,使得到的r 到 j中间的元素都满足要求。具体操作是将r与其子节点的值进行比较,若大于其左右孩子中的较小者,则与其交换,然后进行比较其与其新的孩子。直到r不大于其孩子或到达堆底。

建堆运算CreateHeap将一个以元素序列通过向下调整建成最小堆。调整从位置为(n-2)/2取整数部分(由于堆是一个完全二叉数,对于二叉树,有i节点的父节点为(i-1)/2取整数部分,则这里求的是n-1节点的父节点,也就是自底向上的第一个分支节点)的元素开始,然后重复调用AdjustDown操作,知道下标为0的元素调整完成,则建堆结束。

template <class T>
void AdjustDown(T heap[],int r,int j){
	T temp = heap[r];
	int child = 2 * r + 1;
	while(child < j ){
		child = heap[child] > heap[child+1] ? (child+1) : child;
		if(temp > heap[child]){
			heap[r] = heap[child];
			heap[child] = temp;
			r = child ;
			child = 2 * r + 1;
			temp = heap[r];
		}else
			break;
	}
}
template <class T>
void CreateHeap(T heap[],int n){
	for(int i = n/2 - 1;i>-1;i--)
		AdjustDown(heap,i,n-1);
}

int main()
{
	int A[7] = {99,36,68,72,12,48,02};
	CreateHeap(A,7);
	return 0;
}

每执行一次AdjustDown的时间为O(log2 n)。建堆的时间复杂度为O(n)。