堆-c++
/********************************************************************** *版权所有 (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"); }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。