堆ADT_Heap

一个大小为n的堆是一棵包含n个结点的完全二叉树, 该树中每个结点的关键字值大于等于其双亲结点的关键字值.

堆顶: 二叉树的根, 它的关键字是整棵树上最小的.(最小堆)

建堆运算时, CreatHeap()函数完成将一个以任意次序排列的元素排列, 通过向下调整建成最小堆.

实现运算AdjustDown的方法是: 向下调整heap[r]. 设tmp = hear[r], 如果tmp大于其左, 右孩子中的较小者, 则将tmp与该较小元素交换,

调整后继续将tmp与它的左右孩子比较. 如果比较小的孩子大, 则继续交换. 直到不需要再调整或者已经到堆底.

实现代码:

#include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;
template 
void AdjustDown(T heap[], int r, int j)
{
	int child = 2 * r + 1;
	T tmp = heap[r];
	while(child <= j) {
		if(child < j && heap[child] > heap[child + 1]) child++;
		if(tmp < heap[child]) break;
		heap[(child - 1) / 2] = heap[child];
		child = 2 * child + 1;
	}
	heap[(child - 1) / 2] = tmp;
	for(int i = 0; i <= j; ++i)
		cout << heap[i] << 	;
	cout << endl;
}
template 
void CreatHeap(T heap[], int n)
{
	for(int i = (n - 2) / 2; i > -1; --i)
		AdjustDown(heap, i, n - 1);
}
int main(int argc, char const *argv[])
{
	int heap[] = {61, 28, 81, 43, 36, 47, 83, 5};
	for(int i = 0; i < 8; ++i)
		cout << heap[i] << 	;
	cout << endl;
	CreatHeap(heap, 8);
	return 0;
}