堆

堆是完全二叉树，一个大小为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;
}

堆,布布扣,bubuko.com

堆

原文：http://blog.csdn.net/luo_xianming/article/details/25474173