堆的C语言实现——堆与堆排序（二）

Myth丶恋晨 2022-05-25 02:41 163阅读 0赞

# 堆的C语言实现——堆与堆排序（二） #

*  堆的C语言实现——堆与堆排序（二）
    
     *  头文件
     *  初始化函数
     *  下滤函数1（递归）
     *  堆构造函数1（自底向上，递归）
     *  下滤函数2（非递归，交换法）
     *  下滤函数3（非递归，空穴法）
     *  堆构造函数2（自底向上，非递归，空穴法）
     *  自顶向下堆构造
     *  插入函数1（交换法）
     *  插入函数2（空穴法）
     *  堆构造函数3（自顶向下，空穴法）
     *  删除最大键函数
     *  完整的代码及运行截图

上一篇博文 [堆与堆排序（一）][Link 1]介绍了什么是堆、堆的性质、堆的构造。这篇博文我们以大根堆为例，讨论堆的C语言实现。完整的代码会附在本文末尾。

## 头文件 ##

#ifndef _MAX_HEAP_
    #define _MAX_HEAP_
    
    #define MAX_HEAP_SENTINEL 100
    #define MIN_PQ_CAPACITY 3
    #define HEAP_CAPACITY 20
    
    #define LEFT(i) (2*i)
    #define RIGHT(i) (2*i+1)
    #define PARENT(i) (i/2)
    
    typedef int element_t;
    
    struct heap_struct
    {
        int capacity;
        int size;
        element_t *elements;
    };
    
    typedef struct heap_struct *priority_queue;
    
    void print_array(int a[], int len);
    void print_heap(priority_queue heap);
    
    // 基于空穴法的下滤函数（非递归）
    void percolate_down_no_swap(int a[], int n, int t);
    
    // 基于递归的下滤函数（交换法）
    void percolate_down_recursive(int a[], int n, int t);
    
    // 基于交换法的下滤函数（非递归）
    void percolate_down(int a[], int n, int t);
    
    priority_queue initialize(int capacity);//优先队列初始化
    
    // 基于空穴法的插入
    void insert_no_swap(element_t x, priority_queue max_heap);
    void insert(element_t x, priority_queue max_heap); //基于交换法的插入
    int is_full(priority_queue max_heap);
    int is_empty(priority_queue max_heap);
    element_t delete_max(priority_queue max_heap); // 删除最大节点
    
    // 自底向上的堆构造（递归）,调用了函数 percolate_down_recursive
    priority_queue build_max_heap_bottom_up_recursive(element_t a[], int elmt_cnt);
    // 自底向上的堆构造（非递归），调用了函数 percolate_down_no_swap
    priority_queue build_max_heap_bottom_up(element_t a[], int elmt_cnt);
    // 自顶向下的堆构造（非递归），调用了函数 insert_no_swap
    priority_queue build_max_heap_up_bottom(element_t a[], int elmt_cnt);
    // 自顶向下的堆构造（非递归），调用了函数 insert
    priority_queue build_max_heap_up_bottom2(element_t a[], int elmt_cnt);
    
    void destroy(priority_queue heap);  // 用来释放内存
    #endif

第4行：`#define MAX_HEAP_SENTINEL 100`

在上一篇博文中说过，可以用数组来实现堆。方法是用从上到下、从左到右的方式来记录堆的元素。为了方便起见，可以在这种数组从 1 到 n 的位置上存放堆的元素，留下`H[0]`，要么让它空着，要么在其中放一个限位器，**它的值大于堆中任何一个元素**。 所以我们定义了一个限位器 `MAX_HEAP_SENTINEL`，假设最大堆的任何一个元素都小于100.

14~19行：定义了一个结构体`struct heap_struct`

struct heap_struct
    {
        int capacity;
        int size;
        element_t *elements;
    };

`capacity`表示堆的容量，也就是说节点个数最多就是 `capacity`，不能再多了。

`size`表示当前堆的大小，即当前这个堆有多少个节点。

`elements`是一个指针，指向数组的第一个元素（在初始化函数中会体现这一点）。

## 初始化函数 ##

priority_queue initialize(int capacity)
    {
        priority_queue heap;
    
        if(capacity < MIN_PQ_CAPACITY)
        {
            printf("Priority queue capacity is too small\n");
            exit(EXIT_FAILURE);
        }
    
        heap = malloc( sizeof(struct heap_struct));
        if(heap == NULL)
        {
            printf("out of space\n");
            exit(EXIT_FAILURE);
        }
    
        // +1 是因为要包含[0]
        heap->elements = malloc( (capacity + 1) * sizeof(element_t) );
        if(heap->elements == NULL)
        {
            printf("out of space\n");
            exit(EXIT_FAILURE);
        }
    
        heap->capacity = capacity;
        heap->size = 0;
    #ifdef MAX_HEAP_SENTINEL
        // MAX_HEAP_SENTINEL 大于任何一个节点值，作为标记
        heap->elements[0] = MAX_HEAP_SENTINEL;
    #endif
        return heap;
    }

第11行：为结构体分配内存 `heap = malloc( sizeof(struct heap_struct));`

第19行：为数组分配内存 `heap->elements = malloc( (capacity + 1) * sizeof(element_t) );`

第27行：`heap->size = 0;`

初始化状态，堆的元素数为0，即堆为空。

## 下滤函数1（递归） ##

// 下滤函数（递归解法）
    // 假定以 LEFT(t) 和 RIGHT(t) 为根的子树都已经是大根堆
    // 调整以 t 为根的子树，使之成为大根堆。
    // 节点位置为 1~n，a[0]不使用
    void percolate_down_recursive(int a[], int n, int t) 
    {
    #ifdef PRINT_PROCEDURE
        printf("check %d\n", t);
    #endif
        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下移一层
    #ifdef PRINT_PROCEDURE
            printf("%d NOT satisfied, swap it and %d \n",t, max);
    #endif
            percolate_down_recursive(a, n, max); // 递归，继续考察t
        }
    }

上一篇博文已经说了，对于自底向上构造堆，基本思想如下：

1.  在初始化一棵包含 n 个节点的完全二叉树时，按照给定的顺序来放置键；
2.  按照下面的方法，对树进行“堆化”
3.  从最后一个父母节点开始，到根为止，该算法检查这些节点的键是否满足父母优势的要求。如果该节点不满足，就把该节点的键 K 和它子女的最大键进行交换，然后再检查在新的位置上，K 是否满足父母优势要求。这个过程一直继续到对 K 的父母优势要求满足为止（最终它必须满足，因为对每个叶子中的键来说，这条件是自动满足的）。
4.  对于以当前父母节点为根的子树，在完成它的“堆化”以后，对该节点的直接前趋（数组中此节点的前一个节点）进行同样的操作。在对树的根完成这种操作以后，该算法就停止了。

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

此函数用来实现第3步。有了这个函数，我们就可以写出自底向上构造堆的完整代码了。

## 堆构造函数1（自底向上，递归） ##

// element_t a[]是用户数组 例如 int a[5]={1,3,5,2,4};
    // 则传参 a 和 5
    priority_queue build_max_heap_bottom_up_recursive(element_t a[], int elmt_cnt) 
    {
        priority_queue pq = initialize(elmt_cnt);
        assert(pq != NULL);
    
        // 把用户数组拷贝到堆中
        memcpy(pq->elements+1, a, sizeof(element_t)*elmt_cnt);
        pq->size = elmt_cnt;  
    
        int i;
        // 从最后一个父母节点开始下滤，使成为大根堆
        for(i = elmt_cnt/2; i >= 1; --i)
        {       
            percolate_down_recursive(pq->elements, elmt_cnt, i);
        }
    
        return pq;
    }

`percolate_down_recursive`函数用了递归，虽然很容易理解，但是对自己要求高的程序员看着有点碍眼，能否不用递归呢？当然能，只是要牺牲一点可读性。

## 下滤函数2（非递归，交换法） ##

// 此函数没有用递归
    void percolate_down(int a[], int n, int t) 
    {
        int key = a[t]; // 用key记录当前节点的键值
        int max_idx;
        int heap_ok = 0;  // 初始条件是父母优势不满足
    #ifdef PRINT_PROCEDURE 
        printf("check %d\n", t);
    #endif 
        // LEFT(t) <= n 成立说明有孩子
        while(!heap_ok && (LEFT(t) <= n))
        {           
            max_idx = LEFT(t); // 假设左孩子键值最大
            if(LEFT(t) < n) // 条件成立则说明有2个孩子
            {
                if(a[LEFT(t)] < a[RIGHT(t)])
                    max_idx = RIGHT(t); //说明右孩子的键值比左孩子大
    
            }//此时max_idx指向键值最大的孩子
    
            if(a[t] >= a[max_idx])
            {
                heap_ok = 1; //满足父母优势，跳出循环，本函数返回
            }
            else
            {   //交换位置，a[t]被换到了a[max_idx]的位置
                swap(a+t, a+max_idx); 
    #ifdef PRINT_PROCEDURE 
                printf("%d NOT satisfied, swap it and %d \n",t, max_idx);
                printf("check %d\n", t);
    #endif 
                t = max_idx; //继续考察a[max_idx]是否满足父母优势 
            }               
        }   
        return;
    }

第27行：交换函数的代码是

//交换*a和*b, 内部函数
    static void swap(int* a, int* b) 
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }

可以看到，交换需要3个赋值语句，还是比较费时间的。这里介绍一种“空穴法”，可以避免交换。

如下图所示，1号节点的左子树和右子树都已经是大根堆，这时候需要对1号节点下滤，使以1号节点为根的树成为一个大根堆。

![Image 1][]

![70][]

![70 1][]

![70 2][]

![70 3][]

![70 4][]

## 下滤函数3（非递归，空穴法） ##

// 非递归且不用交换
    void percolate_down_no_swap(int a[], int n, int t) 
    {
        int key = a[t];  // 用key记录键值
        int max_idx;
        int heap_ok = 0;  // 初始条件是父母优势不满足
    #ifdef PRINT_PROCEDURE 
        printf("check %d\n", t);
    #endif 
        // LEFT(t) <= n 成立则说明 t 有孩子
        while(!heap_ok && (LEFT(t) <= n))
        {           
            max_idx = LEFT(t); // 假设左右孩子中，左孩子键值较大
            if(LEFT(t) < n)    // 条件成立则说明有2个孩子
            {
                if(a[LEFT(t)] < a[RIGHT(t)])
                    max_idx = RIGHT(t); //说明右孩子的键值比左孩子大
    
            }//此时max_idx指向键值较大的孩子
    
            if(key >= a[max_idx])
            {
                heap_ok = 1; //为 key 找到了合适的位置，跳出循环
            }
            else
            {   
                a[t] =  a[max_idx]; //孩子上移一层，max_idx 被空出来，成为空穴 
    
    #ifdef PRINT_PROCEDURE 
                printf("use %d fill %d \n", max_idx, t);
                printf("%d is empty\n", max_idx);
    #endif 
                t = max_idx; //令 t 指向空穴 
            }               
        }
    
        a[t] = key; // 把 key 填入空穴
    #ifdef PRINT_PROCEDURE 
        printf("use value %d fill %d \n", key, t);      
    #endif 
        return;
    }

## 堆构造函数2（自底向上，非递归，空穴法） ##

有了上面这个函数，在构造大根堆时，函数可以这样写：

priority_queue build_max_heap_bottom_up(element_t a[], int elmt_cnt) 
    {
        priority_queue pq = initialize(elmt_cnt);
        assert(pq != NULL);
        memcpy(pq->elements+1, a, sizeof(element_t)*elmt_cnt);
        pq->size = elmt_cnt;
    
        int i;
        for(i = elmt_cnt/2; i >= 1; --i)
        {       
            // 下滤，非递归，空穴法
            percolate_down_no_swap(pq->elements, elmt_cnt, i);
        }
        return pq;
    }

## 自顶向下堆构造 ##

除了上面的构造方法，还有一种算法（效率较低）是通过把新的键连续**插入**预先构造好的堆，来构造一个新堆。有的人把它称作自顶向下堆构造。

1.  首先，把一个键值为 K 的新节点附加在当前堆的最后一个叶子后面；
2.  然后，拿 K 和它父母的键做比较。如果 K 小于等于它的父母，那么算法停止；否则交换这两个键，并把 K 和它的新父母做比较。
3.  重复2，一直持续到 K 不大于它的父母，或者 K 成为树根为止。

这种策略叫做**上滤（percolate up）**。

以`4,1,3,2,16,9,10,14,8,7`这列键为例，用图说明上滤的过程。

![70 5][]

![70 6][]

![70 7][]

![70 8][]

![70 9][]

![70 10][]

![70 11][]

## 插入函数1（交换法） ##

void insert(element_t x, priority_queue max_heap)
    {
        if( is_full(max_heap) )
        {
            printf("priority queue is full, insert failed\n");
            return;
        }
        // 把新节点附加在当前堆的最后一个叶子后面
        max_heap->elements[ ++max_heap->size ] = x; 
    
        int cur = max_heap->size; // cur 指向新的节点
    #ifdef MAX_HEAP_SENTINEL
        while( x > max_heap->elements[ cur/2 ] ) // 把新节点的键值和它的父母比较
    #else
        // 当 cur == 1 时，说明新节点已经被交换到了树根的位置，此时应该跳出循环
        while( (cur != 1) && (x > max_heap->elements[ cur/2 ]) )
    #endif
        {
            // 交换新节点和它的父母
            swap(max_heap->elements + cur/2, max_heap->elements + cur);
            cur /= 2;   // cur继续指向新节点
        }
    }

12~17行：这里用了两种写法，如果没有使用限位器`MAX_HEAP_SENTINEL`，那么 `elements[0]`就没有使用，当`cur == 1`的时候，说明节点已经被交换到了根的位置，它没有父母节点，这时候应该停止操作。所以在while的条件判断中加入了`(cur != 1)`.

如果使用了限位器，`elements[0]`中的值是一个比任何节点都大的值。当`cur == 1`的时候，说明节点已经被交换到了根的位置，这时候`elements[ cur/2 ]`就是`elements[0]`，显然while的循环条件不成立，所以循环中止。

同前文一样，swap操作比较费时，函数还可以优化。

## 插入函数2（空穴法） ##

// swap操作比较费时，上面的函数可以优化一下
    
    void insert_no_swap(element_t x, priority_queue max_heap)
    {
        if( is_full(max_heap) )
        {
            printf("priority queue is full, insert failed\n");
            return;
        }
        // 在当前堆的最后一个叶子后面创建一个空穴，用cur指向空穴
        int cur = ++max_heap->size; 
    #ifdef MAX_HEAP_SENTINEL
        while( x > max_heap->elements[ cur/2 ] ) // 新节点的键值和空穴的父母作比较
    #else
        while( (cur != 1) && (x > max_heap->elements[ cur/2 ]) )
    #endif
        {
            // 父母向下移动一层，填补空穴，原父母的位置成为新的空穴
            max_heap->elements[cur] = max_heap->elements[cur/2];
            cur /= 2;   
        }
        max_heap->elements[cur] = x; //把新节点填入空穴
    }

## 堆构造函数3（自顶向下，空穴法） ##

有了插入函数，自顶向下构造堆的函数就不难写了。

priority_queue build_max_heap_up_bottom(element_t a[], int elmt_cnt) 
    {
        priority_queue pq = initialize(elmt_cnt);
        assert(pq != NULL);
    
        int i;
        for(i = 0; i < elmt_cnt; ++i)
        {       
            insert_no_swap(a[i], pq);
    #ifdef PRINT_PROCEDURE
            print_heap(pq);
    #endif
        }
        return pq;
    }

## 删除最大键函数 ##

找出最大的键是容易的，困难的是删除它。当删除一个最大键时，在根位置产生了一个空穴。由于现在堆少了一个元素，因此堆中最后一个元素`X`必须移动到某个地方。如果`X`可以被放到空穴中（满足父母优势），那么删除完成。不过这一般不太可能，因此我们将空穴的两个儿子中较大者移入空穴，这样就把空穴向下推了一层。重复该步骤直到`X`可以被放入空穴中。

因为“用*空穴法*进行下滤”的详细方法在上一篇博文中讲过，所以这里略去了下滤的详细过程。

假设已经构造好了一个大根堆，对应的数组是

`[16,14,10,8,7,3,9,1,4,2]`

下面的一系列图用来演示如何逐个删除最大键。

![这里写图片描述][70 12]

![这里写图片描述][70 13]

![这里写图片描述][70 14]

![这里写图片描述][70 15]

![这里写图片描述][70 16]

![这里写图片描述][70 17]

![这里写图片描述][70 18]

![这里写图片描述][70 19]

![这里写图片描述][70 20]

![这里写图片描述][70 21]

![这里写图片描述][70 22]

![这里写图片描述][70 23]

![这里写图片描述][70 24]

![这里写图片描述][70 25]

![这里写图片描述][70 26]

element_t delete_max(priority_queue max_heap)
    {
        if( is_empty( max_heap ) )
        {
            printf("priority queue is empty, return [0]\n");
            return max_heap->elements[0];
        }
    
        if( max_heap->size == 1)
        {
            max_heap->size = 0;
            return max_heap->elements[1];
        }
        else
        {   
            element_t max_elmt = max_heap->elements[1];
    
            // 得到最后一个元素，并且堆的大小减一
            element_t last_elmt = max_heap->elements[max_heap->size--];
            // 把最后一个元素移动到树根的位置
            max_heap->elements[1] = last_elmt;
            // 调整树根
            percolate_down_no_swap(max_heap->elements,max_heap->size ,1);   
            return max_elmt;
        }
    }

写到这里，重要的函数就讲完了。

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

最后附上完整的代码和测试函数，对了，还有运行截图。

/* max_heap.h */
    #ifndef _MAX_HEAP_
    #define _MAX_HEAP_
    
    #define MAX_HEAP_SENTINEL 100
    #define MIN_PQ_CAPACITY 3
    #define HEAP_CAPACITY 20
    
    #define LEFT(i) (2*i)
    #define RIGHT(i) (2*i+1)
    #define PARENT(i) (i/2)
    
    typedef int element_t;
    
    struct heap_struct
    {
        int capacity;
        int size;
        element_t *elements;
    };
    
    typedef struct heap_struct *priority_queue;
    
    void print_array(int a[], int len);
    void print_heap(priority_queue heap);
    
    void percolate_down_no_swap(int a[], int n, int t);
    void percolate_down_recursive(int a[], int n, int t);
    void percolate_down(int a[], int n, int t);
    
    priority_queue initialize(int capacity);
    void insert_no_swap(element_t x, priority_queue max_heap);
    void insert(element_t x, priority_queue max_heap);
    int is_full(priority_queue max_heap);
    int is_empty(priority_queue max_heap);
    element_t delete_max(priority_queue max_heap);
    
    priority_queue build_max_heap_bottom_up_recursive(element_t a[], int elmt_cnt);
    priority_queue build_max_heap_bottom_up(element_t a[], int elmt_cnt);
    priority_queue build_max_heap_up_bottom(element_t a[], int elmt_cnt);
    priority_queue build_max_heap_up_bottom2(element_t a[], int elmt_cnt);
    void destroy(priority_queue heap);
    #endif

/* max_heap.c */
    #include "max_heap.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    void print_heap(priority_queue heap)
    {
        if(heap->size == 0)
        {
            printf("the priority queue is empty\n");
            return;
        }
    
        // +1是因为heap->size不包括elements[0]
        print_array(heap->elements, heap->size + 1);
    }
    
    
    // 打印下标和元素值的通用函数
    void print_array(int a[], int len)
    {
    
        printf("index:\n");
        int i;
        for (i = 0; i < len; ++i) 
        {
            printf("%3d ", i); //宽度3加上空格就是4，所以后面有 4 * len
        } 
        printf("\n");
        for (int i = 1; i <= 4 * len; ++i) 
        {
            printf("%s", "-");
        } 
        printf("\n");
        // 以上2个for循环用于打印数组下标和分隔线“-----------”
    
    
        for(i=0; i<len; ++i)
            printf("%3d ",a[i]); //打印数组的值
        printf("\n\n");
    }
    
    
    //交换*a和*b, 内部函数
    static void swap(int* a, int* b) 
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    priority_queue initialize(int capacity)
    {
        priority_queue heap;
    
        if(capacity < MIN_PQ_CAPACITY)
        {
            printf("Priority queue capacity is too small\n");
            exit(EXIT_FAILURE);
        }
    
        heap = malloc( sizeof(struct heap_struct));
        if(heap == NULL)
        {
            printf("out of space\n");
            exit(EXIT_FAILURE);
        }
    
        // +1 是因为要包含[0]
        heap->elements = malloc( (capacity + 1) * sizeof(element_t) );
        if(heap->elements == NULL)
        {
            printf("out of space\n");
            exit(EXIT_FAILURE);
        }
    
        heap->capacity = capacity;
        heap->size = 0;
    #ifdef MAX_HEAP_SENTINEL
        // MAX_HEAP_SENTINEL 大于任何一个节点值，作为标记
        heap->elements[0] = MAX_HEAP_SENTINEL;
    #endif
        return heap;
    }
    
    void destroy(priority_queue heap) // 别忘了释放内存！
    {
        free(heap->elements);
        free(heap); 
    }
    
    int is_full(priority_queue max_heap)
    {
        return (max_heap->size == max_heap->capacity);
    }
    
    int is_empty(priority_queue max_heap)
    {
        return (max_heap->size == 0);
    }
    
    
    
    // 下滤函数（递归解法）
    // 假定以 LEFT(t) 和 RIGHT(t) 为根的子树都已经是大根堆
    // 调整以 t 为根的子树，使之成为大根堆。
    // 节点位置为 1~n，a[0]不使用
    void percolate_down_recursive(int a[], int n, int t) 
    {
    #ifdef PRINT_PROCEDURE
        printf("check %d\n", t);
    #endif
        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下移一层
    #ifdef PRINT_PROCEDURE
            printf("%d NOT satisfied, swap it and %d \n",t, max);
    #endif
            percolate_down_recursive(a, n, max); // 递归，继续考察t
        }
    }
    
    // 2018-5-4 8:17
    // 此函数没有用递归
    void percolate_down(int a[], int n, int t) 
    {
        int key = a[t]; // 用key记录当前节点的键值
        int max_idx;
        int heap_ok = 0;  // 初始条件是父母优势不满足
    #ifdef PRINT_PROCEDURE 
        printf("check %d\n", t);
    #endif 
        // LEFT(t) <= n 成立说明有孩子
        while(!heap_ok && (LEFT(t) <= n))
        {           
            max_idx = LEFT(t); // 假设左孩子键值最大
            if(LEFT(t) < n) // 条件成立则说明有2个孩子
            {
                if(a[LEFT(t)] < a[RIGHT(t)])
                    max_idx = RIGHT(t); //说明右孩子的键值比左孩子大
    
            }//此时max_idx指向键值最大的孩子
    
            if(a[t] >= a[max_idx])
            {
                heap_ok = 1; //满足父母优势，跳出循环，本函数返回
            }
            else
            {   //交换位置，a[t]被换到了a[max_idx]的位置
                swap(a+t, a+max_idx); 
    #ifdef PRINT_PROCEDURE 
                printf("%d NOT satisfied, swap it and %d \n",t, max_idx);
                printf("check %d\n", t);
    #endif 
                t = max_idx; //继续考察a[max_idx]是否满足父母优势 
            }               
        }   
        return;
    }
    
    // 非递归且不用交换
    void percolate_down_no_swap(int a[], int n, int t) 
    {
        int key = a[t];  // 用key记录键值
        int max_idx;
        int heap_ok = 0;  // 初始条件是父母优势不满足
    #ifdef PRINT_PROCEDURE 
        printf("check %d\n", t);
    #endif 
        // LEFT(t) <= n 成立则说明 t 有孩子
        while(!heap_ok && (LEFT(t) <= n))
        {           
            max_idx = LEFT(t); // 假设左右孩子中，左孩子键值较大
            if(LEFT(t) < n)    // 条件成立则说明有2个孩子
            {
                if(a[LEFT(t)] < a[RIGHT(t)])
                    max_idx = RIGHT(t); //说明右孩子的键值比左孩子大
    
            }//此时max_idx指向键值较大的孩子
    
            if(key >= a[max_idx])
            {
                heap_ok = 1; //为 key 找到了合适的位置，跳出循环
            }
            else
            {   
                a[t] =  a[max_idx]; //孩子上移一层，max_idx 被空出来，成为空穴 
    
    #ifdef PRINT_PROCEDURE 
                printf("use %d fill %d \n", max_idx, t);
                printf("%d is empty\n", max_idx);
    #endif 
                t = max_idx; //令 t 指向空穴 
            }               
        }
    
        a[t] = key; // 把 key 填入空穴
    #ifdef PRINT_PROCEDURE 
        printf("use value %d fill %d \n", key, t);
    
    #endif 
    
        return;
    }
    
    void insert(element_t x, priority_queue max_heap)
    {
        if( is_full(max_heap) )
        {
            printf("priority queue is full, insert failed\n");
            return;
        }
        // 把新节点附加在当前堆的最后一个叶子后面
        max_heap->elements[ ++max_heap->size ] = x; 
    
        int cur = max_heap->size; // cur 指向新的节点
    #ifdef MAX_HEAP_SENTINEL
        while( x > max_heap->elements[ cur/2 ] ) // 把新节点的键值和它的父母比较
    #else
        // 当 cur == 1 时，说明新节点已经被交换到了树根的位置，此时应该跳出循环
        while( (cur != 1) && (x > max_heap->elements[ cur/2 ]) )
    #endif
        {
            // 交换新节点和它的父母
            swap(max_heap->elements + cur/2, max_heap->elements + cur);
            cur /= 2;   // cur继续指向新节点
        }
    
    }
    
    // swap操作比较费时，上面的函数可以优化一下
    
    void insert_no_swap(element_t x, priority_queue max_heap)
    {
        if( is_full(max_heap) )
        {
            printf("priority queue is full, insert failed\n");
            return;
        }
        // 在当前堆的最后一个叶子后面创建一个空穴，用cur指向空穴
        int cur = ++max_heap->size; 
    #ifdef MAX_HEAP_SENTINEL
        while( x > max_heap->elements[ cur/2 ] ) // 新节点的键值和空穴的父母作比较
    #else
        while( (cur != 1) && (x > max_heap->elements[ cur/2 ]) )
    #endif
        {
            // 父母向下移动一层，填补空穴，原父母的位置成为新的空穴
            max_heap->elements[cur] = max_heap->elements[cur/2];
            cur /= 2;   
        }
        max_heap->elements[cur] = x; //把新节点填入空穴
    
    }
    
    
    
    
    
    
    // element_t a[]是用户数组 例如 int a[5]={1,3,5,2,4};
    // 则传参 a 和 5
    priority_queue build_max_heap_bottom_up_recursive(element_t a[], int elmt_cnt) 
    {
        priority_queue pq = initialize(elmt_cnt);
        assert(pq != NULL);
    
        memcpy(pq->elements+1, a, sizeof(element_t)*elmt_cnt);
        pq->size = elmt_cnt;  
    
        int i;
        // 从最后一个父母节点开始堆化
        for(i = elmt_cnt/2; i >= 1; --i)
        {       
            percolate_down_recursive(pq->elements, elmt_cnt, i);
        }
    
        return pq;
    }
    
    priority_queue build_max_heap_bottom_up(element_t a[], int elmt_cnt) 
    {
        priority_queue pq = initialize(elmt_cnt);
        assert(pq != NULL);
        memcpy(pq->elements+1, a, sizeof(element_t)*elmt_cnt);
        pq->size = elmt_cnt;
    
        int i;
        for(i = elmt_cnt/2; i >= 1; --i)
        {       
            percolate_down_no_swap(pq->elements, elmt_cnt, i);
        }
        return pq;
    }
    
    priority_queue build_max_heap_up_bottom(element_t a[], int elmt_cnt) 
    {
        priority_queue pq = initialize(elmt_cnt);
        assert(pq != NULL);
    
        int i;
        for(i = 0; i < elmt_cnt; ++i)
        {       
            insert_no_swap(a[i], pq);
    #ifdef PRINT_PROCEDURE
            print_heap(pq);
    #endif
        }
        return pq;
    }
    
    
    //和上一个函数的区别是插入采用交换法
    priority_queue build_max_heap_up_bottom2(element_t a[], int elmt_cnt) 
    {
        priority_queue pq = initialize(elmt_cnt);
    
    
        int i;
        for(i = 0; i < elmt_cnt; ++i)
        {       
            insert(a[i], pq);
        }
        return pq;
    }
    
    
    
    element_t delete_max(priority_queue max_heap)
    {
        if( is_empty( max_heap ) )
        {
            printf("priority queue is empty, return [0]\n");
            return max_heap->elements[0];
        }
    
        if( max_heap->size == 1)
        {
            max_heap->size = 0;
            return max_heap->elements[1];
        }
        else
        {   
            element_t max_elmt = max_heap->elements[1];
    
            // 得到最后一个元素，并且大小减一
            element_t last_elmt = max_heap->elements[max_heap->size--];
            // 把最后一个元素移动到树根的位置
            max_heap->elements[1] = last_elmt;
            // 调整树根
            percolate_down_no_swap(max_heap->elements,max_heap->size ,1);
    
            return max_elmt;
        }
    }
    
    //测试函数
    int main(void)
    {
        int a[]={
       4,1,3,2,16,9,10,14,8,7}; //10个
        int elmt_cnt = sizeof(a) / sizeof(a[0]);
    
        priority_queue pq1,pq2,pq3,pq4;
    
        // 测试最大堆构造函数
        pq1 = build_max_heap_bottom_up_recursive(a,elmt_cnt);
        pq2 = build_max_heap_bottom_up(a,elmt_cnt); 
        pq3 = build_max_heap_up_bottom(a,elmt_cnt);
        pq4 = build_max_heap_up_bottom2(a,elmt_cnt);
    
        // 打印构造结果
        print_heap(pq1);
        print_heap(pq2);
        print_heap(pq3);
        print_heap(pq4);
    
        // 测试删除最大键的函数
        int del_key = 0;
    
        printf("delete the max key: ");
        while(is_empty(pq3)==0) // 用pq3测试
        {
            del_key = delete_max(pq3);
            printf("%d ", del_key);
        }
        printf("\n");
    
        destroy(pq1); //别忘了释放内存！
        destroy(pq2);
        destroy(pq3);
        destroy(pq4);   
    
        return 0;   
    }

![这里写图片描述][70 27]

[Link 1]: https://blog.csdn.net/longintchar/article/details/80211137
[Image 1]: 
[70]: /images/20220525/2931ec8002784ffd86a77986159aa34b.png
[70 1]: /images/20220525/a078a4e3da8842bc823d660dd03ca237.png
[70 2]: /images/20220525/01df014823464733bb5b765097195337.png
[70 3]: /images/20220525/b6f98ddeb60445a58149699d71cfe039.png
[70 4]: /images/20220525/c4a68bc286114073af75373254c90674.png
[70 5]: /images/20220525/0c67584cdf414c2ea63086856a4f135d.png
[70 6]: /images/20220525/f17b0e52f86a445aafd2276d6bc5f107.png
[70 7]: /images/20220525/07661feb2c18485b9cf2d3312d7130a5.png
[70 8]: /images/20220525/a00167e172454273888b109604770930.png
[70 9]: /images/20220525/9eda85f51ac8427daeb37191e5710311.png
[70 10]: /images/20220525/784ea9dc89c54276afa93850070024eb.png
[70 11]: /images/20220525/c661c3ac5ff444f2850a9f67c28a7bf5.png
[70 12]: /images/20220525/4c2ebd5bd0d84e98a0603e40dc85f49f.png
[70 13]: /images/20220525/aaed63f524634eb0adc7884186cd1b26.png
[70 14]: /images/20220525/d132da0f38c74ec0a78b4de71be0f51b.png
[70 15]: /images/20220525/1e6109a9be224ac68633f9fbcd7c0886.png
[70 16]: /images/20220525/0665b5abd95a4f2fb88c2a33b4025d06.png
[70 17]: /images/20220525/3b65d453865044ac8854f0b7a3b946cb.png
[70 18]: /images/20220525/debf4c7f582743f5a5b0afd7d68f7bf3.png
[70 19]: /images/20220525/4c7b1e5967ed44f9aa45061324e41412.png
[70 20]: /images/20220525/2bd808f11b464b6aba19ccacb6ebebda.png
[70 21]: /images/20220525/b9058b4c574b42778690da3348ac90f3.png
[70 22]: /images/20220525/e49ac0ac703948acb24fda1a3d48267c.png
[70 23]: /images/20220525/01339dd404bc4a26a97b7c8bf7b8737e.png
[70 24]: /images/20220525/04f60e65648845a39496e61e6e090d1e.png
[70 25]: /images/20220525/369be19915da4cc3bbacf0faae673297.png
[70 26]: /images/20220525/da268b828feb41f09334658248170df6.png
[70 27]: /images/20220525/336111046f124be3bd0830763a0d80d0.png