了解什么是堆

什么是堆，堆的定义是：n个元素的序列，{k1,k2,k3,…,kn},当且满足如下关系式，称为堆。

ki < k2i && ki < k2i+1

ki > k2i && ki > k2i+1

如下所示：

如何利用堆来排序

将一个无序序列建成堆

堆看作是一个完全二叉树，堆就完全满足二叉树的五个性质，如果不清楚的可以去看看二叉树的性质。

从堆中最后一个非终点[n / 2] 个元素，向前慢慢筛选，一直到[ 1 ],

如何输出堆顶元素后，调整剩余元素为堆

如果是每一个父节点都对左右孩子节点打的，就是大根堆，可知，堆顶的元素就是最大的，相反的话，就是小根堆，堆顶元素就是最小的。

大根堆用来做顺序，每次将堆顶的元素，和堆尾的元素交换，然后将剩下的节点变成大根堆，最后一个元素就变成了最大的。小根堆相反。

合适的代码实现

数据的基本类型

采用自定义结构体类型，将别的记录都简化，只留下关键部分。类似数据库中的一条记录，中只保留关键字，依据关键字来排序。

typedef struct

{

int key;

// float name;

// elemtype anothing;

} recnode;

定义MySort类来实现。运算符重载实现了，可以直接输入和输出的功能。中间还没注意多写了一个插入拍寻的函数。当然现在的重点是堆排序了。

两个函数，Shift， 和 HeapSort。

class MySort

{

private:

recnode rec[MAXSIZE];

int len;

public:

void SeleSort(); // 选择排序

void Shift(int i,int m); // 堆排序的建立大顶碓的函数

void HeapSort(); // 堆排序

friend ostream &operator<<(ostream &,const MySort &); // 输入

friend istream &operator>>(istream &,MySort &); // 输出

};

两个函数，Shift， 和 HeapSort。

说一说对Shift的理解，Shift有两个参数，i 和 m ， i 是根节点的编号 ， （父节点的编号），m 是最后一个节点的编号。从 i 节点往下，层次筛选，找到比 i 节点左右孩子节点大的节点就将 i 节点 的值换成 大的节点。依次向下。

void MySort::Shift(int i,int m){

// i 是根节点的编号 ， （父节点的编号）

// m 是最后一个节点的编号

int j;

recnode temp = rec[i];

j = 2 * i; // j 是左孩子

while (j <= m) {

// j 是左右都有节点的 较大值

// 为什么不是 j <= m 呢，因为当 j = m 时，只有一个节点

if ( j < m && rec[j].key < rec[j + 1].key)

j++;

if (temp.key < rec[j].key) {

rec[i] = rec[j];

i = j;

j = 2 * i;

}

else break;

}

rec[i] = temp;

}

然后是HeapSort函数，为什么第一次循环是从，数组的长度的一半开始呢？堆可以看做事一个完全二叉树，二叉树的性质中有，长度为 N 完全二叉树， 节点标号为 N/2的元素，一定在上一层，即一定是度为 0 或 1 的节点。

利用Shift（N/2,N）一定将此节点完美的建成一个大小根堆。循环向上一直到堆的根节点，可以将以个无序的数组建成大小根堆。

由于根堆的性质，堆顶元素一定是最大或者最小的，将堆顶的元素和最后一个元素互换，那么堆最后一个元素一定也是最大或者最小的，然后将剩余的元素（除堆最后一个元素），重新建成一个大小根堆，第一次筛选完成。然后以此向下即可。

void MySort::HeapSort(){

int i;

int n = len;

recnode temp;

for( i = n / 2; i >= 1; i--)

Shift(i,n);

for( i = n; i >= 2; i--)

{

temp = rec[1];

rec[1] = rec[i];

rec[i] = temp;

Shift(1,i - 1);

}

}

为了输入输出的方便，利用C++的特性，将运算符重载会方便许多，附上代码。

ostream &operator<<(ostream & output,const MySort &c){

for(int i = 1; i <= c.len; i++)

{

output << c.rec[i].key << " ";

}

output << endl;

return output;

}

istream &operator>>(istream & input,MySort &c){

int i,k = 0;

cout << "输入数据,以空格隔开,0 结束" << endl;

input >> i;·2

while ( i ) {

k++;

c.rec[k].key = i;

input >> i;

}

c.len = k;

return input;

}

主函数调用：

int main(int argc,char const *argv[])

{

MySort a ;

cin >> a;

a.HeapSort();

cout << a ;

return 0;

}

结果如下

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!