目录

一、堆的定义

二、堆与序列的关系

三、算法思想

3.1 建立初始堆

3.2 重建堆

3.2.1 过程分析

3.2.2 算法实现

3.3 堆排序

二、堆与序列的关系

堆排序是在排序过程中将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录。

即仍采用向量数组方式存储待排序记录，并非采用树的存储结构，而仅仅是采用完全二叉树的顺序结构的特征进行分析。

注：弃用一维数组的0号位置。

---

三、算法思想

堆排序过程主要解决两个问题：

1、按堆定义建立初始堆；

2、去掉最大元素后重建堆。

3.1 建立初始堆

sift函数被调用一次，就完成一个子树的调整。

使用循环反复调用该函数，自底层向上逐层把子树调整为堆，最终把无序序列建成一个堆。

void create_heap(RecordType r[], int length) {
    
    
    for (int k = length / 2; k >= 1; --i)
        sift(r, k, length); 
}

 

                               第一次循环                                                                第二次循环 

 

                                 第三次循环                                                                第四次循环 

---

3.2 重建堆

3.2.1 过程分析

以其中一棵子树的重建为例，作出以下说明。

伪代码：
for (k = length /2; k >= 1; --k)
    sift(r, k, length);
|
|
void sift(RecordType r[], int k, int length) {
    i = k; j = 2 * i;
    while (j < length) {
        if (j < length && r[j] < r[j+1])
            j++;
        if (r[i] < r[j])
            r[i] <---> r[j];
        i = j;
        j = 2 * i;
    }
}

sift函数内第一次循环：i = 2，j = 4；r[i] < r[j] 成立，进行交换；i = 4，j = 8。

 

sift函数内第二次循环：i = 4，j = 8；r[i] < r[j] 成立，进行交换；i = 8，j = 16。

此时不满足循环条件，跳出循环，该子树重建完成。

---

3.2.2 算法实现

void sift(RecordType r[], int k, int m) {
    
    RecordType t = r[k];
    bool finished = false;

    int i = k; 
    int j = 2 * i;  

    while (j <= m && !finished) {
        
        if (j < m && r[j].key < r[j + 1].key)
            ++j;
        
        if (t.key >= r[j].key)
            finished = true;
        else {
            
            r[i] = r[j];
            
            i = j;
            j = 2 * i;
        }
    }
    
    r[i] = t;
}

---

3.3 堆排序

算法思想：

1、将待排序记录按照堆的定义建立初始堆，并输出堆顶元素；

2、调整剩余的记录序列，利用筛选法将前 length-i 个元素重新筛选建成一个新堆，再输出堆顶元素；

3、重复执行步骤2，进行 length-1 次筛选，最后使待排序记录序列成为一个有序的序列。

void HeapSort(RecordType r[], int length) {
    RecordType b;

    
    create_heap(r, length);

    for (int i = length; i >= 2; --i) {
        
        b = r[1];
        r[1] = r[i];
        r[i] = b;

        
        sift(r, 1, i - 1);
    }
}

说明：初始堆为大顶堆，将堆顶记录和最后一个记录互换后，对于剩下的 i-1 个元素构成的堆，只有以1为根结点的子树不是大顶堆，其余子树均为大顶堆，因此只用对该子树进行重建。