当前位置:编程学习 > 网站相关 >>

数据结构——堆排序

html">数据结构——堆排序

堆排序总结


堆排序思想:最大堆的堆顶元素是全部数据中的最大值,输出这个值
。再将剩余元素整理成新的最大堆,此时堆顶元素有时又是剩余元素
的最大值,再输出这个值。继续这个过程,每次输出堆顶元素,并将
剩余元素整理成新的最大堆再输出...

堆排序要解决的几个问题
1:如何将数据排列成堆的形式——初始堆的建立
2:输出堆顶元素后,剩余元素如何再整理成新的堆——堆的整理
3:输出元素放在什么位置

预备知识:
1: 堆中的元素存储在一个数组中,根据堆中的各元素之间具有
有序性关系,可以使用二叉树的方式来表示一个堆。因为各元素从前
至后存放在数组的钱n 个单元中,所以所画的二叉树实际上是一颗完全
二叉树
2: 所以根据完全二叉树的性质,数组前一半的数据都是分值节点,后一半
的数据都是叶子节点
3: 即如果有七个数,分别占据数组的a[1]-a[7],那么7/2=3,所以a[1],
    a[2],a[3]为分支节点,剩下的为叶子节点
4: a[i]的左儿子为a[i*2],右儿子为a[i*2+1],如a[1]的左右儿子分别为
    a[2]与a[3]。(这有赖于数组从a[0]开始,还是从a[1]开始)

建堆的过程:
    见代码,见实例图

1 /*********************************************************/
2  /*数组从下标1开始*/
3
4 #include<iostream>
5  #define L(t) ((t)<<1)
6 #define R(t) ((t)<<1 | 1)
7 usingnamespace std;
8
9 intconst NUMBER = 1000;
10 int trees[NUMBER];
11 int N;
12 /*********************************************************/
13 void swap(int &a,int &b){
14 int temp = a;
15 a = b;
16 b = temp;
17 }
18 /*********************************************************/
19 //a[i]元素向下沉,此时堆中的实际元素为n,被甩在后面的元素
20 //已经不用管了
21 void ShiftDown(int i,int n){
22 int child;
23 //i<=n/2说明trees[i]为分支结点
24 //i=child;该句在循环最后执行,即从上往下递归判断
25 //新的位置是否已经稳定,不稳定继续下沉
26 for(;i<=n/2;i=child){
27 child = i*2;//先试着将预交换的元素设为左儿子
28 if((child != n) && trees[child+1]>trees[child])
补充:综合编程 , 其他综合 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,