看懂堆排序——堆与堆排序（三）

偏执的太偏执、 2022-05-25 06:52 280阅读 0赞

# 看懂堆排序——堆与堆排序（三） #

*  看懂堆排序——堆与堆排序（三）
    
     *  堆排序的基本思想
     *  代码详解
        
         *  父亲下标和孩子下标的关系
         *  打印数组的函数
         *  下滤函数
         *  构造堆的函数
         *  删除最大元函数
         *  排序主函数
     *  完整代码及运行截图
 *  参考资料

有了前面两篇文章的铺垫，

[堆与堆排序（一）][Link 1]

[堆与堆排序（二）][Link 2]

我们终于可以学习“堆排序”了。

假使给定一个数组`a[N]`，其包含元素`a[0]`,`a[1]`,`a[2]`,…,`a[N-1]`，现要将其中元素按升序排列。如果利用堆这种数据结构，你会怎么做?

## 堆排序的基本思想 ##

很自然地想到，首先把此数组构造成一个小根堆（利用原来的数组，原地构造），然后依次删除最小元素，直至堆为空。为了存储每次删除的最小元素，我们需要一个额外的数组，待堆为空的时候，把额外数组的内容拷贝到原来的数组。

这种方法可行吗？当然可行。但是需要一个额外的数组，当数组很大时，这个空间开销是非常可观的。避免使用额外的数组的聪明做法是意识到这样一个事实：在每次删除最小元素之后，堆的规模缩小了1. 因此，位于堆中最后的那个单元可以用来存放刚刚删去的元素。具体来说，堆排序的步骤如下：

1.  为给定的序列创建一个堆（本文以最大堆为例）
2.  交换堆的第一个元素`a[0]`和最后一个元素`a[n-1]`
3.  堆的大小减`1`（`--n`）。如果 `n==1`，算法停止；否则，对`a[0]`进行下滤
4.  重复2~3步

## 代码详解 ##

### 父亲下标和孩子下标的关系 ###

因为待排序的数组一般都是从0开始，而不是从1开始，所以之前讨论的父节点和孩子节点之间的关系需要修改。

之前的是：

![70][]

对于数组任一位置 `i` 上的元素，其左儿子在位置 `2i` 上，右儿子在`2i+1`上，它的父亲则在位置 ⌊i/2⌋  ⌊ i / 2 ⌋ 上。

**现在的是**：  
![这里写图片描述][70 1]

对于数组任一位置 `i` 上的元素，其左儿子在位置 `2i+1` 上，右儿子在`2i+2`上，它的父亲则在位置 ⌊(i−1)/2⌋  ⌊ ( i − 1 ) / 2 ⌋ 上。

以节点 D 为例，D 的下标是 3.

*  `B`是它的父节点，`B`的下标是 1（= ⌊(3−1)/2⌋  ⌊ ( 3 − 1 ) / 2 ⌋ ），如图中黑色的线；
 *  `H`是它的左孩子，`H`的下标是 7（= 2∗3\+1  2 ∗ 3 + 1 ），如图中蓝色的线；
 *  `I`是它的右孩子，`I`的下标是 8（= 2∗3\+2  2 ∗ 3 + 2 ），如图中红色的线；

所以，我们的宏定义是：

#define LEFT(i) (2*i+1)
    #define RIGHT(i) (2*i+2)
    #define PARENT(i) ((i-1)/2)

### 打印数组的函数 ###

void print_array_debug(int a[], int len, int pos, char token)
    {
        for(int i=0; i<len; ++i)
        {
            if( i == pos )
            {
                printf("%c %d ", token, a[i]); //打印元素值和记号
            }
            else
            {
                printf("%3d ",a[i]); //正常打印
            }
        }
        printf("\n\n");
    }

为了展示出排序的过程，我设计了这个函数。其实这个函数和普通的打印函数差不多，无非就是多了一个在某个元素前面打印一个标记的功能。比如要在`a[0]`的前面打印一个`'*'`，那么可以这样调用（假设数组长度是10）：

`print_array_debug(a, 10, 0, '*');`

如果不想用它的打印标记功能，则可以给`pos`传一个负数，给`token`随便什么值都行。比如

#define DUMMY_POS -1
    #define DUMMY_TOKEN '\0'

然后调用

`print_array_debug(a, 10, DUMMY_POS, DUMMY_TOKEN);`

### 下滤函数 ###

对于给定的数列，我们首先要对其进行“堆化”，堆化的方法如下：

1.  在初始化一棵包含 n 个节点的完全二叉树时，按照给定的顺序来放置键；
2.  从最后一个父母节点开始，到根为止，检查这些父母节点的键是否满足父母优势。如果该节点不满足，就把该节点的键 K 和它子女的最大键进行交换，然后再检查在新的位置上，K 是否满足父母优势。这个过程一直继续到 K 满足父母优势为止（最终它必须满足，因为对每个叶子中的键来说，这条件是自动满足的）。

**如果该节点不满足父母优势，就把该节点的键 K 和它子女的最大键进行交换，然后再检查在新的位置上，K 是否满足父母优势。这个过程一直继续到 K 满足父母优势为止——这种策略叫做下滤（percolate down）**。

// 下滤函数（递归解法）
    // 假定以 LEFT(t) 和 RIGHT(t) 为根的子树都已经是大根堆
    // 调整以 t 为根的子树，使之成为大根堆。
    // 节点位置为 [0], [1], [2], ..., [n-1]
    void percolate_down_recursive(int a[], int n, int t) 
    {   
        int left = LEFT(t);
        int right = RIGHT(t);   
        int max = t; //假设当前节点的键值最大
    
        if(left < n)  // 说明t有左孩子 
        {
            max = a[left] > a[max] ? left : max;
        }
    
        if(right < n)  // 说明t有右孩子 
        {
            max = a[right] > a[max] ? right : max;
        }
    
        if(max != t)
        {   
            swap(a + max, a + t); // 交换t和它的某个孩子，即t被换到了max位置
            percolate_down_recursive(a, n, max); // 递归，继续考察t
        }
    }

### 构造堆的函数 ###

// 自底向上建堆，下滤法
    void build_max_heap(element_t a[], int n) 
    {   
        int i;
        // 从最后一个父母节点开始下滤，一直到根节点
        for(i = PARENT(n); i >= 0; --i)
        {       
            percolate_down_recursive(a, n, i);
        }
    }

### 删除最大元函数 ###

//把最大元素和堆末尾的元素交换位置，堆的规模减1，再下滤根节点
    void delete_max_to_end(int heap[], int heap_size)
    {
        if(heap_size == 2) // 当剩下2个节点的时候，交换后不用下滤
        {
            swap( heap + 0, heap + 1 );     
        }
        else if(heap_size > 2)
        {
            swap( heap + 0, heap + heap_size - 1 );
            percolate_down_recursive(heap, heap_size-1, 0);
        }
        return;
    }

### 排序主函数 ###

void heap_sort(int a[], int length)
    {
        build_max_heap(a,length); //堆的构造
    #ifdef PRINT_PROCEDURE
        printf("build the max heap:\n");
        print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN);
    #endif
        for(int size=length; size>=2; --size) //当堆的大小为1时，停止
        {
            delete_max_to_end(a,size);
    #ifdef PRINT_PROCEDURE 
            print_array_debug(a, ELMT_NUM, size-1, '|');
    #endif
        }
    }

## 完整代码及运行截图 ##

#include <stdio.h>
    
    #define LEFT(i) (2*i+1)
    #define RIGHT(i) (2*i+2)
    #define PARENT(i) ((i-1)/2)
    #define ELMT_NUM 10
    #define DUMMY_POS -1
    #define DUMMY_TOKEN '\0'
    
    typedef int element_t;
    
    void print_array_debug(int a[], int len, int pos, char token)
    {
        for(int i=0; i<len; ++i)
        {
            if( i == pos )
            {
                printf("%c %d ", token, a[i]); //打印元素值和记号
            }
            else
            {
                printf("%3d ",a[i]); //正常打印
            }
        }
        printf("\n\n");
    }
    
    //交换*a和*b
    void swap(int* a, int* b) 
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    // 下滤函数（递归解法）
    // 假定以 LEFT(t) 和 RIGHT(t) 为根的子树都已经是大根堆
    // 调整以 t 为根的子树，使之成为大根堆。
    // 节点位置为 [0], [1], [2], ..., [n-1]
    void percolate_down_recursive(int a[], int n, int t) 
    {   
        int left = LEFT(t);
        int right = RIGHT(t);   
        int max = t; //假设当前节点的键值最大
    
        if(left < n)  // 说明t有左孩子 
        {
            max = a[left] > a[max] ? left : max;
        }
    
        if(right < n)  // 说明t有右孩子 
        {
            max = a[right] > a[max] ? right : max;
        }
    
        if(max != t)
        {   
            swap(a + max, a + t); // 交换t和它的某个孩子，即t被换到了max位置
            percolate_down_recursive(a, n, max); // 递归，继续考察t
        }
    }
    
    // 自底向上建堆，下滤法
    void build_max_heap(element_t a[], int n) 
    {   
        int i;
        // 从最后一个父母节点开始下滤，一直到根节点
        for(i = PARENT(n); i >= 0; --i)
        {       
            percolate_down_recursive(a, n, i);
        }
    }
    
    //把最大元素和堆末尾的元素交换位置，堆的规模减1，再下滤根节点
    void delete_max_to_end(int heap[], int heap_size)
    {
        if(heap_size == 2) // 当剩下2个节点的时候，交换后不用下滤
        {
            swap( heap + 0, heap + 1 );     
        }
        else if(heap_size > 2)
        {
            swap( heap + 0, heap + heap_size - 1 );
            percolate_down_recursive(heap, heap_size-1, 0);
        }
        return;
    }
    
    void heap_sort(int a[], int length)
    {
        build_max_heap(a,length);
    #ifdef PRINT_PROCEDURE
        printf("build the max heap:\n");
        print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN);
    #endif
        for(int size=length; size>=2; --size)
        {
            delete_max_to_end(a,size);
    #ifdef PRINT_PROCEDURE 
            print_array_debug(a, ELMT_NUM, size-1, '|');
    #endif
        }
    }
    
    int main(void)
    {
        int a[ELMT_NUM]={
       4,1,3,2,16,9,10,14,8,7}; //10个
        printf("the array to be sorted:\n ");   
        print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN);
    
        heap_sort(a,ELMT_NUM);
    
        printf("sort finished:\n ");
        print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN);
    }

假设文件名为`heap_sort.c`,编译：

gcc heap_sort.c -DPRINT_PROCEDURE

运行结果如下图：  
![这里写图片描述][70 2]

图中竖线右边的是已经有序的元素，竖线左边是堆。

【本系列完】

# 参考资料 #

【1】《数据结构与算法分析（原书第2版）》（机械工业出版社，2004）  
【2】《算法设计与分析基础（第3版）》（清华大学出版社，2015）

[Link 1]: https://blog.csdn.net/longintchar/article/details/80211137
[Link 2]: https://blog.csdn.net/longintchar/article/details/80219062
[70]: /images/20220525/2c62394bf0e040e18a51cedac065813f.png
[70 1]: /images/20220525/8873bb23355e45e3b4f73b171b24abb4.png
[70 2]: /images/20220525/d053298b03af451c96fd411b01d1cc5b.png