了解什么是堆

什么是堆，堆的定义是：n个元素的序列，{k₁ ,k₂,k₃,…,k_n},当且满足如下关系式，称为堆。
k_i < k_2i && k_i < k_2i+1

k_i > k_2i && k_i > k_2i+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;
}
结果如下