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

《最大堆实现排序(从大到小输出)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、最大堆实现排序（从大到小输出）示例输入（11个数，第一个数表示元素个数）：100123456789示例输出：9876543210堆和优先队列在计算机科学中，堆是一种经过排序的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，也用于排序算法，如堆排序。优先队列(priorityqueue)，不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。优先队列是0个或多个元素的集合，每个

2、元素都有一个优先权或值。最大堆MaxHeap在起始索引为0的堆中1)堆的根节点将存放在位置02)节点i的左子节点在位置2*i+13)节点i的右子节点在位置2*i+24)节点i的父节点在位置floor((i-1)/2)SiftUp(inti)：第i个元素上移，最多执行logn次元素比较；对堆中某个关键字进行修改，大于父结点键值时，执行上移操作，恢复堆的性质。SiftDown(inti)：第i个元素下移；对堆中某个关键字进行修改，与其子结点中值较大的一个进行比较，小于子结点键值时，执行下移操作，恢复堆的性质。Push(Type

3、x):在队列中追加元素；堆大小增加1，元素放在堆的末端，执行向上筛选。Pop():弹出元素；弹出最大（最小）堆的首元素，满足优先性质。Top():取得首元素元素值；取得最大（最小）堆的首元素，满足优先性质。堆排序可利用堆性质，对序列进行排序。假定数组A元素个数为n，数组构建为堆后，根据最大堆性质，根结点A[0]即为最大元素；交换A[0]、A[n-1]，A[n-1]为最大元素；相当于删掉A[n-1]，堆元素个数减1；交换到A[0]的元素破坏了堆的性质，需对A[0]作下筛操作，恢复堆的结构；此时元素个数为n-1；继续，直至元素

4、个数为1。源代码：//科目：算法设计//题目：最大堆实现排序（从大到小输出）//语言：C++//作者：武叶//创作时间：2012年4月13日#includeusingnamespacestd;#defineM100voidset_low(intp,intinsert[],int&size);voidheap_sort(intinsert[],intsize);intdel_max(intinsert[],int&size);voidbuilt_num(intinsert[],int&size);intm

5、ain(){intinsert[M],size;//insert为输入数组，size为数组大小cin>>size;for(inti=1;i<=size;i++)cin>>insert[i];built_num(insert,size);heap_sort(insert,size);for(intj=1;j<=size;j++)cout<

6、根元素下调q为左子节点while(q<=size){if(qinsert[q])q++;if(insert[q]

7、size){for(inti=size/2;i>0;i--)set_low(i,insert,size);}voidheap_sort(intinsert[],intsize)//insert为待处理数组，n为该数组的实际大小{intn=size;int*insert2=newint[size];intindex=1;while(size){insert2[index++]=del_max(insert,size);}for(intj=1;j<=n;j++)insert[j]=insert2[j];size=n;}运行结果

8、截图：答销网真情提供：：：：：www.daxiao51.com文章出处：：：：http://www.daxiao51.com/forum.php?mod=viewthread&tid=1535&page=1&extra=#pid2403