二叉堆

hq8501

　　根据算法导论里的伪代码实现



#include <iostream>
using namespace std;
void exchange(int a[], int i, int j)
{
int temp = a;
a = a[j];
a[j] = temp;
}
void adjustTree(int a[], int i, int total)
{
int l = i * 2;
int r = i * 2 + 1;
//取左右孩子中最大的
int maxIndex = -1;
if(l <= total && a[l] > a)
{
maxIndex = l;
}
else
maxIndex = i;
if(r <= total && a[r] > a[maxIndex])
{
maxIndex = r;
}
if(maxIndex != i)
{
exchange(a, i, maxIndex);
//TODO 优化
adjustTree(a, maxIndex, total);
}
}
void buildTree(int a[], int total)
{
　　
　　//含有n个元素的堆,第一个叶子结点是(n/2)+1,从最后一个不是叶子结点的点开始调整堆
　　　　//初始化,刚开始i=length/2,从length/2+1.......length都是叶子结点,只有一个元素,满足二叉堆的定义(循环不变式)
　　　　//保持:每一个的调整都是父结点和左右孩子之间的递归调整,此时以i作为根结点的左右子树都是一个二叉堆,
　　　　//它们满足二叉堆的定义(循环不变式),
　　　　//终止:终止条件i=0,i=1.....i=n,每一个1,2.....n都是一个最大堆的根结点,(满足二叉堆的定义)

　　　　for(int i = total / 2; i >= 1; i--)
{
adjustTree(a, i, total);
}
}
/**
* 大堆
*/
int main()
{
int a[] = { 0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
int total = 10;
buildTree(a, total);
for(int i = 1; i <= total; i++)
cout << " " << a;
cout << endl;
int t2 = total;
for(int i = total; i >= 2; i--)
{
exchange(a, 1, t2);
t2--;
adjustTree(a, 1, t2);
}
for(int i = 1; i <= total; i++)
cout << " " << a;
cout << endl;
return 0;
}