【数据结构 C 语言实现】堆和优先队列

1 堆

1.1 堆是什么

    堆是一种特殊的完全二叉树，可以轻便地使用数组表示和维护。堆适合于需要维护最值的场景，根据其维护的最值种类，可分为 最小堆 和 最大堆 两类，也有很多别的叫法。

• 最大堆：每个父节点的值 ≥ 其子节点的值，根节点是最大值。
  
• 最小堆：每个父节点的值 ≤ 其子节点的值，根节点是最小值。
  

1.2 基本操作

    堆的基本操作主要有 构建堆，向上调解（上浮），向下调解（下沉） 等操作。此中 构建堆 操作是指将一个不是堆的数组转换为堆，本质上是由 下沉 操作组成的。
    下面以构建 最小堆 为例。
1.2.1 向上调解（上浮）

    假如某个元素 x 比其父结点的元素值 p 更小，则其不满足最小堆的定义，需要调解。以 x 为研究对象，则应该将 x 与其父结点元素值 p 做交换，直到满足最小堆的定义为止。
    以上操作从一棵树的角度来看，相当于将 x 向上调解了。下面是详细的算法步骤：
    1 堆 h 是一个整型数组，长度为 n，需要调解的元素下标为 i，注意下标从 0 开始；
    2 计算父结点下标，易知 i 的父结点下标 p 为 (i-1)/2 向下取整，假如 p >= 0 && h < h[p]，则进行交换 swap(h, h[p])，然后将研究对象转移到父结点上：i = p，循环；否则退出循环，表示已经浮到顶了。其伪代码如下：

1. adjust_up(h, i):
2.         if i < 0 or i >= h.length:
3.                 return
4.         p = (i-1)/2
5.         while p >= 0 && h[i] < h[p]:
6.                 swap(h[p], h[i])
7.                 i = p
8.                 p = (i-1)/2

复制代码

1.2.2 向下调解（下沉）

    假如某个元素 a 比其父结点的元素值 p 更小，则其不满足最小堆的定义，需要调解。以其 父结点 p 为研究对象，则应该将 p 与其子结点元素值的最小值 x 做交换，直到满足最小堆的定义为止。
    以上操作从一棵树的角度来看，相当于将 p 向下调解了。下面是详细的算法步骤：
    1 堆 h 是一个整型数组，长度为 n，需要调解的元素下标为 i，注意下标从 0 开始；
    2 计算左子结点下标，易知 i 的左子结点下标 l 为 i * 2 + 1，假如 i 还有右子结点，则应该比较左右子结点的值的巨细，取最小的谁人结点 c，然后进行交换 swap(h, h[c])，然后将研究对象转移到该子结点上：i = c，循环；否则退出循环，表示已经沉到底了。其伪代码如下：

1. adjust_down(h, i):
2.         if i < 0 or i >= h.length:
3.                 return
4.         l = 2*i+1
5.         while l < h.length:
6.                 if l + 1 < h.length && h[l+1] < h[l]:
7.                         l++
8.                 if h[i] <= h[l]:
9.                         return
10.                 swap(h[l], h[i])
11.                 i = l
12.                 l = 2*i+1

复制代码

1.2.3 构建堆

    给你一个无序数组，怎么将其酿成堆呢？
    首先我们知道，堆是完全二叉树，其末了一个非叶结点的下标是可以确定的，假设堆 h 是一个整型数组，长度为 n，下标从 0 开始，则其末了一个非叶结点的下标是 (n-1)/2 向下取整。
    为什么要关注末了一个非叶结点呢？因为从这个结点按照从右到左的顺序依次将元素下沉，直到操作完成，一个堆就建立好了。（每一次只会在一个满足定义的“堆”上面增加一个不确定的结点，那么将这个结点向下沉即可保证以该结点为根的堆是满足定义的）。
    也就是调用大约 n/2 次下沉操作即可，算法步骤和伪代码省略。
1.3 参考代码

    假设堆中元素为 int 整数，堆为最小堆。
1.3.1 上浮

1. void adjust_up(int* h, int pos) {
2.     while (pos > 0 && h[pos] < h[(pos - 1) >> 1]) {
3.         swap(&h[pos], &h[(pos - 1) >> 1]);
4.         pos = (pos - 1) >> 1;
5.     }
6. }

复制代码

1.3.2 下沉

1. void adjust_down(int* h, int pos, int n) {
2.     int k = (pos << 1) + 1;
3.     while (k < n) {
4.         if (k + 1 < n && h[k + 1] < h[k]) {
5.             k++;
6.         }
7.         if (h[pos] <= h[k]) {
8.             break;
9.         }
10.         swap(&h[pos], &h[k]);
11.         pos = k;
12.         k = (pos << 1) + 1;
13.     }
14. }

复制代码

1.3.3 构建堆

1. void heaplify(int* arr, int n) {
2.     for (int i = (n - 1) / 2; i >= 0; i--) {
3.         adjust_down(arr, i);
4.     }
5. }

复制代码

2 优先队列

    固然我们常常将堆和优先队列混淆在一起说，但不得不搞清晰的是，优先队列算是堆的一种应用。我们平时用的“堆”这种数据结构，大多数是指的优先队列。
    优先队列需要具备 上浮 和 下沉 这两个堆的基本操作，还要有 入队 和 出队 这两个队列的基本操作。
2.1 基本操作

2.1.1 出队

    优先队列的出队操作即将堆数组的第一个元素即堆顶返回，然后将堆数组的末了一个元素放到堆顶处，然后将堆顶的元素向下调解，并将堆的巨细减一。
2.1.2 入队

    优先队列的入队操作即在堆数组的末了添加一个元素，堆的巨细加一，然后将此时堆数组的末了一个元素（新元素）向上调解。
2.2 代码实现

    这里将记录一个通用的以 C 语言实现的优先队列代码。

1. // 头文件省略
3. /** C 语言之 “泛型” **/
4. #define ElemType Message*
6. /** 优先队列元素: 结构体 **/
7. typedef struct _msg {
8.     int priority;
9.     char s[15];
10. } Message;
12. /** 优先队列结构体定义 **/
13. typedef struct _priority_queue {
14.     ElemType* data;
15.     int size, capacity;
16. } PriorityQueue;
18. /** 自定义比较函数 **/
19. int cmp(ElemType a, ElemType b) { return a->priority - b->priority; }
21. /** 交换两个元素 **/
22. void swap(ElemType* a, ElemType* b) {
23.     ElemType t = *a;
24.     *a = *b;
25.     *b = t;
26. }
28. /** 初始化优先队列 **/
29. PriorityQueue* init_pq(int n) {
30.     PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
31.     if (!pq) {
32.         return NULL;
33.     }
34.     pq->capacity = n;
35.     pq->size = 0;
36.     pq->data = (ElemType*)malloc(pq->capacity * sizeof(ElemType));
37.     return pq;
38. }
40. /** 销毁优先队列 **/
41. void destroy_pq(PriorityQueue* pq) {
42.         if (pq) {
43.             for (int i = 0; i < pq->size; i++) {
44.                 free(pq->data[i]);
45.             }
46.             free(pq->data);
47.             free(pq);
48.    }
49. }
51. /** 上浮 **/
52. void adjust_up(PriorityQueue* pq, int pos) {
53.     while (pos > 0 && cmp(pq->data[pos], pq->data[(pos - 1) >> 1]) < 0) {
54.         swap(&pq->data[pos], &pq->data[(pos - 1) >> 1]);
55.         pos = (pos - 1) >> 1;
56.     }
57. }
59. /** 下沉 **/
60. void adjust_down(PriorityQueue* pq, int pos) {
61.     int k = 0;
62.     while ((pos << 1) + 1 < pq->size) {
63.         k = (pos << 1) + 1;
64.         if (k + 1 < pq->size && cmp(pq->data[k + 1], pq->data[k]) < 0) {
65.             k++;
66.         }
67.         if (cmp(pq->data[pos], pq->data[k]) <= 0) {
68.             break;
69.         }
70.         swap(&pq->data[pos], &pq->data[k]);
71.         pos = k;
72.     }
73. }
75. /** 入队 **/
76. void push(PriorityQueue* pq, ElemType msg) {
77.     if (pq->size == pq->capacity) {
78.         pq->capacity <<= 1;
79.         pq->data =
80.             (ElemType*)realloc(pq->data, pq->capacity * sizeof(ElemType));
81.     }
82.     pq->data[pq->size] = msg;
83.     adjust_up(pq, pq->size++);
84. }
86. /** 出队 **/
87. ElemType pop(PriorityQueue* pq) {
88.     if (pq->size == 0) {
89.         return NULL;
90.     }
91.     ElemType ans = pq->data[0];
92.     pq->data[0] = pq->data[--pq->size];
93.     adjust_down(pq, 0);
94.     return ans;
95. }

复制代码

3 总结

    上面只是以最小堆作为例子，别的的环境可以此类推，而且数组下标从 0 开始，也可以将数组下标从 1 开始，如许做的唯一优点就是计算父亲和儿子的下标时的表达式更轻便一些，只需要选择一个自己喜欢的即可。
    关于优先队列的基本操作，这里省略了相对来说不太紧张的基本操作（没有封装成函数），有兴趣可以自己封装一下。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。