/**********************************************************************
*版权所有 (C)2014, cy。
*
*文件名称：堆.cpp 
*内容摘要：无
*其它说明：无
*当前版本： V1.0
*作    者：cheng yang
*完成日期： 20140624
*
*  版本       修改时间     修改人           修改内容
********************************************************************
*   V1.0        20140624    cy			   创建
**********************************************************************/
#include <iostream>
using namespace std;

//字段最大长度
const int MAXSIZE = 10000;
int a[MAXSIZE] = {0};
int heapsize = 0;

//函数声明
inline void swap(int i , int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;

}

//获得i节点的父亲节点下标
inline int Parent(int i) 
{
	return i >> 1;
}

//左孩子节点的下标
inline int Left(int i)
{
	return i << 1;
}

//右孩子节点的下标
inline int Right(int i)
{
	return (i << 1) + 1;
}


/**********************************************************************
*功能描述：保持堆的性质
*输入参数：数组a[]的下标
*输出参数：无
*返回值：无 
*其它说明：无
*修改日期        版本号            修改人         修改内容
* --------------------------------------------------------------
* 
***********************************************************************/
void MaxHeapify(int i)
{
	int left = Left(i);
	int right= Right(i);
	int largest = 0;
	if (left <= heapsize && a[left] > a[i])
	{
		largest = left;
	}
	else
	{
		largest = i;
	}
	if (right <= heapsize && a[right] > a[largest])
	{
		largest = right;
	}
	if (largest != i)
	{
		swap(i, largest);
		MaxHeapify(largest);
	}
}

/**********************************************************************
*功能描述：建堆
*输入参数：指向全局数组的指正 arr*
堆的大小 n
*输出参数：无
*返回值：无
*其它说明：无
*修改日期        版本号            修改人         修改内容
* --------------------------------------------------------------
*
***********************************************************************/
void BuildHeapify(int *arr, const int n)
{
	heapsize = n;
	for (int i = heapsize / 2; i >= 0; i--)
	{
		MaxHeapify(i);
	}
}

/****************************************************************
*功能描述:  主函数                                             *
*输入参数:  无                                                 *
*输出参数:  无                                                 *
*返回值  ：无                                                 *
*其他说明:  无                                                 *
*修改日期        版本号       修改人        修改内容
* -------------------------------------------------------------------------------
* 
****************************************************************/
int main()
{	
	int i = 0;
	while (cin >> a[i++])//为什么i会比实际输入的多出2个，输入3个数（a[0]--a[2]）,可i=4；？？

	BuildHeapify(a, i-2);
	for (int j =i-2 ; j >= 0; j--)
	{
		cout << a[0] << endl;
		swap(0, j);
		heapsize--;
		MaxHeapify(0);
	}

	system("pause");
}

堆-c++,布布扣,bubuko.com

堆-c++