最大堆实现排序(从大到小输出).docVIP

最大堆实现排序（从大到小输出）示例输入（11个数，第一个数表示元素个数）：100123456789示例输出：9876543210堆和优先队列在计算机科学中，堆是一种经过排序的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，也用于排序算法，如堆排序。优先队列(priority queue)，不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。优先队列是0个或多个元素的集合，每个元素都有一个优先权或值。最大堆MaxHeap在起始索引为 0 的堆中1)堆的根节点将存放在位置 0 2)节点i的左子节点在位置2*i+13)节点i的右子节点在位置2*i+24)节点i的父节点在位置floor(i-1)/2)SiftUp(int i)：第i个元素上移，最多执行logn次元素比较；对堆中某个关键字进行修改，大于父结点键值时，执行上移操作，恢复堆的性质。SiftDown(int i)：第i个元素下移；对堆中某个关键字进行修改，与其子结点中值较大的一个进行比较，小于子结点键值时，执行下移操作，恢复堆的性质。Push(Type x):在队列中追加元素；堆大小增加1，元素放在堆的末端，执行向上筛选。Pop():弹出元素；弹出最大（最小）堆的首元素，满足优先性质。Top():取得首元素元素值；取得最大（最小）堆的首元素，满足优先性质。堆排序可利用堆性质，对序列进行排序。假定数组A元素个数为n，数组构建为堆后，根据最大堆性质，根结点A0即为最大元素；交换A0、An-1，An-1为最大元素；相当于删掉An-1，堆元素个数减1；交换到A0的元素破坏了堆的性质，需对A0作下筛操作，恢复堆的结构；此时元素个数为n-1；继续，直至元素个数为1。源代码：/科目：算法设计/题目：最大堆实现排序（从大到小输出）/语言：C+/作者：武叶/创作时间：2012年4月13日#includeusing namespace std;#define M 100void set_low(int p,int insert,int &size);void heap_sort(int insert,int size) ; int del_max(int insert,int &size);void built_num(int insert,int &size);int main() int insertM,size; /insert为输入数组，size为数组大小cinsize; for(int i=1;iinserti; built_num(insert,size); heap_sort(insert,size); for(int j=1;j=size;j+) coutinsertjendl;return 0;void set_low(int p,int insert,int &size) int q=p1, a=insertp; /将下标为p的根元素下调 q为左子节点 while(q=size) if(qinsertq)q+; if(insertqa) break; insertp=insertq; p=q; q=p0;i-) set_low(i,insert,size);void heap_sort(int insert,int size) /insert为待处理数组，n为该数组的实际大小 int n=size; int * insert2=new intsize; int index=1; while(size) insert2index+=del_max(insert,size); for(int j=1;j=n;j+) insertj=insert2j; size=n;运行结果截图：答销网真情提供：www.daxiao51.