AHA'S BOOK

优先队列（priority queue）是最重要的元素始终位于最前面的队列。与普通队列不同的是，优先队列中的元素并不是按照先进先出的顺序进行处理，而是根据其优先级决定处理顺序，具有较高优先级的元素会优先被处理。
优先队列可以是最大优先队列（最大的元素在前）或最小优先队列（最小的元素在先）。优先队列对于需要处理大数据量，并且需要反复确定哪一个现在是最大的或最小（最重要）的数据的算法非常有用。

优先队列的实现方式

在实现上，优先队列可以使用不同的数据结构来实现，例如堆、二叉搜索树、有序动态数组等。

  1. 使用有序动态数组实现：将最重要的数据放在数组的末尾。
    • 缺点：插入新数据很慢，因为插入的数据必须保证数组依然有序。这就需要利用二分搜索算法确定插入的位置，并使用线性时间向后移动数组，以便新数据插入到那里。
  2. 使用平衡二叉树实现：这对于构建双端优先队列非常有用，因为它同时有效地实现了「查找最小值」和「查找最大值」（最重要和最不重要）。
  3. 使用堆实现：堆是实现优先队列的天然数据结构。事实上，堆和优先队列这两个术语经常被用作同义词。
    • 优点：堆比有序动态数组更有效，因为堆只需部分排序，堆的插入和删除操作都是 O(log n) 时间复杂度。

使用堆来实现优先队列是最常见和高效的方式。

基于堆实现优先队列

数据结构之堆基础与堆结构（数组实现）介绍了堆的基本理论知识和最大堆的实现。因此，我们基于这篇文章中实现的最大堆，进行简单的修改，实现优先队列这种数据结构。

优先队列结构定义

为了体现堆中数据的复杂性，不再使用整形数值作为堆中的数据，而是使用结构体作为堆中的数据节点。

1
2
3
4
5
6
7
8
9
10
11
// 定义堆中的数据, 不同优先级的待学习课程
typedef struct Node {
    int priority;
    char *course;
} Node_t;

typedef struct Heap {
    Node_t *heap;   // 堆的数组
    int size;       // 堆的当前大小
    int capacity;   // 堆的容量
} PriorityQueue_t;

优先队列完整代码

这里，我们直接给出优先队列数据结构的完整代码，不明白的函数可以参考 数据结构之堆基础与堆结构（数组实现）中对应的小节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// 定义堆中的数据, 不同优先级的待学习课程
typedef struct Node {
    int priority;
    char *course;
} Node_t;

typedef struct Heap {
    Node_t *heap;   // 堆的数组
    int size;       // 堆的当前大小
    int capacity;   // 堆的容量
} PriorityQueue_t;

PriorityQueue_t* initPriorityQueue(int capacity) {
    if (capacity <= 0) {
        return NULL;
    }
    PriorityQueue_t *queue = (PriorityQueue_t *)malloc(sizeof(PriorityQueue_t));
    queue->heap = (Node_t *)malloc(capacity * sizeof(Node_t));
    queue->size = 0;
    queue->capacity = capacity;
    return queue;
}

int getParentIndex(int index) {
    return (index - 1) >> 1;
}

int getLeftChildIndex(int index) {
    return (index << 1) + 1;
}

int getRightChildIndex(int index) {
    return (index << 1) + 2;
}

void swap(Node_t *s1, Node_t *s2) {
    Node_t temp = *s1;
    memcpy(s1, s2, sizeof(Node_t));
    memcpy(s2, &temp, sizeof(Node_t));
}

void siftUp(PriorityQueue_t *queue, int index) {
    Node_t *heap = queue->heap;
    int parentIndex = getParentIndex(index);
    while ((index > 0) && (heap[index].priority > heap[parentIndex].priority)) {
        swap(&(heap[index]), &(heap[parentIndex]));
        index = parentIndex;  // 交换节点后, 更新当前节点的位置
        parentIndex = getParentIndex(index);  // 重新获取父节点位置
    }
}

void siftDown(PriorityQueue_t* queue, int index) {
    int maxIndex = index;
    int leftChildIndex = getLeftChildIndex(index);
    int rightChildIndex = getRightChildIndex(index);

    // 接下来的两个判断为找出具有更大值的孩子的索引
    if (leftChildIndex < queue->size && queue->heap[leftChildIndex].priority > queue->heap[maxIndex].priority) {
        maxIndex = leftChildIndex;
    }

    if (rightChildIndex < queue->size && queue->heap[rightChildIndex].priority > queue->heap[maxIndex].priority) {
        maxIndex = rightChildIndex;
    }

    if (index != maxIndex) {
        swap(&(queue->heap[index]), &(queue->heap[maxIndex]));
        siftDown(queue, maxIndex);  // 递归方式
    }
}

void push(PriorityQueue_t *queue, Node_t *node) {
    if (queue->size >= queue->capacity) {
        printf("Queue is full!\n");
        return;
    }
    queue->heap[queue->size] = *node;  // 存储在堆数组的最后一个索引后面
    siftUp(queue, queue->size);  // 进行堆化中的上浮操作
    queue->size++;
}

void peek(PriorityQueue_t *queue, Node_t* top) {
    if (queue->size <= 0) {
        memset(top, 0, sizeof(Node_t));
        printf("Queue is empty!\n");
    } else {
        memcpy(top, &(queue->heap[0]), sizeof(Node_t));
    }
}

void pop(PriorityQueue_t *queue, Node_t* top) {
    if (queue->size <= 0) {
        memset(top, 0, sizeof(Node_t));
        printf("Queue is empty!\n");
    } else {
        memcpy(top, &(queue->heap[0]), sizeof(Node_t));
        queue->heap[0] = queue->heap[queue->size - 1];
        queue->size--;
        siftDown(queue, 0);
    }
}

void printPriorityQueue(PriorityQueue_t *queue) {
    printf("Priority queue:\n");
    for (int i = 0; i < queue->size; ++i) {
        printf("    %s: %d\n", queue->heap[i].course, queue->heap[i].priority);
    }
}

void destroyPriorityQueue(PriorityQueue_t *queue) {
    free(queue->heap);
    free(queue);
}

int main(int argc, char *argv[]) {
    int size = 10, capacity = 10;
    Node_t node[] = {
        {2, "Computer Science"},
        {7, "Discrete Mathematics"},
        {26, "Data Structures and Algorithms"},
        {25, "Operating Systems"},
        {19, "C Programming Languages"},
        {17, "Computer Networks"},
        {1, "Database Management Systems"},
        {90, "Artificial Intelligence"},
        {3, "Linear Algebra"},
        {36, "Calculus"}
    };
    PriorityQueue_t *queue = initPriorityQueue(capacity);
    Node_t *topNode = (Node_t *)malloc(sizeof(Node_t));
    memset(topNode, 0, sizeof(Node_t));

    for (int i = 0; i < size; ++i) {
        push(queue, &(node[i]));
    }
    printPriorityQueue(queue);

    peek(queue, topNode);
    if (topNode->course && topNode != 0) {
        printf("Priority queue top course: %s\n", topNode->course);
    }

    pop(queue, topNode);
    if (topNode->course && topNode != 0) {
        printf("Priority queue pop course: %s\n", topNode->course);
    }
    printPriorityQueue(queue);

    for (int i = 0; i < size; ++i) {
        pop(queue, topNode);
        if (topNode->course && topNode != 0) {
            printf("Priority queue pop course: %s\n", topNode->course);
        }
    }
    
    free(topNode);
    destroyPriorityQueue(queue);
    return 0;
}

程序的输出结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Priority queue:
    Artificial Intelligence: 90
    Calculus: 36
    Computer Networks: 17
    Operating Systems: 25
    Data Structures and Algorithms: 26
    Discrete Mathematics: 7
    Database Management Systems: 1
    Computer Science: 2
    Linear Algebra: 3
    C Programming Languages: 19
Priority queue top course: Artificial Intelligence
Priority queue pop course: Artificial Intelligence
Priority queue:
    Calculus: 36
    Data Structures and Algorithms: 26
    Computer Networks: 17
    Operating Systems: 25
    C Programming Languages: 19
    Discrete Mathematics: 7
    Database Management Systems: 1
    Computer Science: 2
    Linear Algebra: 3
Priority queue pop course: Calculus
Priority queue pop course: Data Structures and Algorithms
Priority queue pop course: Operating Systems
Priority queue pop course: C Programming Languages
Priority queue pop course: Computer Networks
Priority queue pop course: Discrete Mathematics
Priority queue pop course: Linear Algebra
Priority queue pop course: Computer Science
Priority queue pop course: Database Management Systems
Queue is empty!

在这个代码中，你可能已经注意到函数 peek 和 pop 的返回值类型是 void，且增加了一个入参 Node_t *。这是因为，这里实现的堆优先队列中存储的是复杂的结构体，我们在获取堆顶数据或弹出堆顶数据时，需要保存数据的所有内容。完成这个目的可以考虑以下两种方式：

  1. 增加一个 Node_t * 入参：将外部申请的一块空间的地址传进来，用于保存堆顶数据，同时也可以处理堆优先队列为空的分支。这种方式，在读取数据及时的情况下，可以实现重复利用这块空间。
  2. 将函数 peek 和 pop 的返回值修改为 Node_t *：这种方式需要在函数内部 malloc 一块空间用于保存返回的数据块，后续需要由用户手动释放每次函数调用所申请的空间，避免内存泄漏。
    • 这种方式，需要多次 malloc 申请空间和多次 free 释放空间，且没有尽可能地遵循谁申请谁释放的原则。
    • 我们不能将堆顶的地址直接作为函数的返回值，因为堆顶的地址的数据是不固定的（在堆化时会被修改）。

参考资料：

  1. Priority Queue in swift-algorithm-club
aha
2023-10-19
数据结构 优先队列
Expand all Back to top Go to bottom Search in blogs
银河白
豆沙绿
杏仁黄
青草绿
秋叶褐