C语言实现优先队列：从基础到最佳实践

简介

在计算机科学中，优先队列是一种特殊的数据结构，它与普通队列的区别在于，优先队列中的元素按照某种优先级进行排序，优先级高的元素先出队。这种特性使得优先队列在许多算法和应用场景中发挥着重要作用，比如图算法（如Dijkstra算法求最短路径）、任务调度系统等。本文将详细介绍如何使用C语言实现优先队列，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一重要的数据结构。

目录

1. 优先队列基础概念
   • 什么是优先队列
   • 优先队列与普通队列的区别
2. C语言实现优先队列的方法
   • 基于数组的实现
   • 基于链表的实现
   • 基于堆的实现（推荐）
3. 常见实践
   • 优先队列在排序算法中的应用
   • 优先队列在图算法中的应用
4. 最佳实践
   • 内存管理优化
   • 性能优化
   • 代码结构优化
5. 小结
6. 参考资料

优先队列基础概念

什么是优先队列

优先队列是一种抽象数据类型，它维护着一组元素，每个元素都有一个优先级。在优先队列中，当执行出队操作时，具有最高优先级的元素会被移除，而不是像普通队列那样按照先进先出（FIFO）的顺序移除元素。

优先队列与普通队列的区别

普通队列遵循FIFO原则，即最早进入队列的元素最早出队。而优先队列则根据元素的优先级来决定出队顺序，优先级高的元素先出队，与元素进入队列的时间顺序无关。

C语言实现优先队列的方法

基于数组的实现

基于数组实现优先队列是一种简单直接的方法。我们可以将元素存储在数组中，每次插入新元素时，将其放在数组末尾，然后通过线性搜索找到最高优先级的元素进行出队操作。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} PriorityQueue;

// 初始化优先队列
void initPriorityQueue(PriorityQueue *pq) {
    pq->size = 0;
}

// 插入元素
void enqueue(PriorityQueue *pq, int value) {
    if (pq->size == MAX_SIZE) {
        printf("优先队列已满\n");
        return;
    }
    pq->data[pq->size++] = value;
}

// 移除并返回最高优先级的元素
int dequeue(PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("优先队列已空\n");
        return -1;
    }
    int maxIndex = 0;
    for (int i = 1; i < pq->size; i++) {
        if (pq->data[i] > pq->data[maxIndex]) {
            maxIndex = i;
        }
    }
    int maxValue = pq->data[maxIndex];
    for (int i = maxIndex; i < pq->size - 1; i++) {
        pq->data[i] = pq->data[i + 1];
    }
    pq->size--;
    return maxValue;
}

int main() {
    PriorityQueue pq;
    initPriorityQueue(&pq);
    enqueue(&pq, 3);
    enqueue(&pq, 1);
    enqueue(&pq, 4);
    printf("出队元素: %d\n", dequeue(&pq)); // 输出 4
    return 0;
}

基于链表的实现

基于链表实现优先队列可以动态地分配和释放内存，避免了数组实现中可能的溢出问题。插入元素时，需要遍历链表找到合适的位置插入，以保持优先级顺序。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
} PriorityQueue;

// 初始化优先队列
void initPriorityQueue(PriorityQueue *pq) {
    pq->front = NULL;
}

// 插入元素
void enqueue(PriorityQueue *pq, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (pq->front == NULL || value > pq->front->data) {
        newNode->next = pq->front;
        pq->front = newNode;
        return;
    }

    Node *current = pq->front;
    while (current->next!= NULL && current->next->data > value) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
}

// 移除并返回最高优先级的元素
int dequeue(PriorityQueue *pq) {
    if (pq->front == NULL) {
        printf("优先队列已空\n");
        return -1;
    }
    int value = pq->front->data;
    Node *temp = pq->front;
    pq->front = pq->front->next;
    free(temp);
    return value;
}

int main() {
    PriorityQueue pq;
    initPriorityQueue(&pq);
    enqueue(&pq, 3);
    enqueue(&pq, 1);
    enqueue(&pq, 4);
    printf("出队元素: %d\n", dequeue(&pq)); // 输出 4
    return 0;
}

基于堆的实现（推荐）

堆是一种完全二叉树，它的每个节点的值都大于或等于其子节点的值（最大堆）或小于或等于其子节点的值（最小堆）。基于堆实现优先队列具有较高的效率，插入和删除操作的时间复杂度均为O(log n)。

#include <stdio.h>
#include <stdlib.h>

#define INITIAL_CAPACITY 100

typedef struct {
    int *data;
    int size;
    int capacity;
} PriorityQueue;

// 初始化优先队列
PriorityQueue* createPriorityQueue() {
    PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));
    pq->data = (int *)malloc(INITIAL_CAPACITY * sizeof(int));
    pq->size = 0;
    pq->capacity = INITIAL_CAPACITY;
    return pq;
}

// 交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 上浮操作
void upHeapify(PriorityQueue *pq, int index) {
    while (index > 0 && pq->data[(index - 1) / 2] < pq->data[index]) {
        swap(&pq->data[(index - 1) / 2], &pq->data[index]);
        index = (index - 1) / 2;
    }
}

// 插入元素
void enqueue(PriorityQueue *pq, int value) {
    if (pq->size == pq->capacity) {
        pq->capacity *= 2;
        pq->data = (int *)realloc(pq->data, pq->capacity * sizeof(int));
    }
    pq->data[pq->size] = value;
    upHeapify(pq, pq->size);
    pq->size++;
}

// 下沉操作
void downHeapify(PriorityQueue *pq, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < pq->size && pq->data[left] > pq->data[largest]) {
        largest = left;
    }

    if (right < pq->size && pq->data[right] > pq->data[largest]) {
        largest = right;
    }

    if (largest!= index) {
        swap(&pq->data[index], &pq->data[largest]);
        downHeapify(pq, largest);
    }
}

// 移除并返回最高优先级的元素
int dequeue(PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("优先队列已空\n");
        return -1;
    }
    int maxValue = pq->data[0];
    pq->size--;
    pq->data[0] = pq->data[pq->size];
    downHeapify(pq, 0);
    return maxValue;
}

// 释放优先队列内存
void freePriorityQueue(PriorityQueue *pq) {
    free(pq->data);
    free(pq);
}

int main() {
    PriorityQueue *pq = createPriorityQueue();
    enqueue(pq, 3);
    enqueue(pq, 1);
    enqueue(pq, 4);
    printf("出队元素: %d\n", dequeue(pq)); // 输出 4
    freePriorityQueue(pq);
    return 0;
}

常见实践

优先队列在排序算法中的应用

优先队列可以用于实现堆排序算法。堆排序的基本思想是将数组构建成一个最大堆，然后依次取出堆顶元素并调整堆结构，从而实现排序。

#include <stdio.h>
#include <stdlib.h>

// 交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 下沉操作
void downHeapify(int *arr, int n, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest!= index) {
        swap(&arr[index], &arr[largest]);
        downHeapify(arr, n, largest);
    }
}

// 堆排序
void heapSort(int *arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        downHeapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        downHeapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

优先队列在图算法中的应用

在Dijkstra算法中，优先队列用于存储顶点到源点的距离，每次取出距离最小的顶点进行扩展，从而找到从源点到其他所有顶点的最短路径。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 9

typedef struct {
    int vertex;
    int distance;
} Node;

typedef struct {
    Node *data[V];
    int size;
} PriorityQueue;

// 初始化优先队列
void initPriorityQueue(PriorityQueue *pq) {
    pq->size = 0;
}

// 交换两个节点
void swap(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

// 上浮操作
void upHeapify(PriorityQueue *pq, int index) {
    while (index > 0 && pq->data[(index - 1) / 2]->distance > pq->data[index]->distance) {
        swap(&pq->data[(index - 1) / 2], &pq->data[index]);
        index = (index - 1) / 2;
    }
}

// 插入节点
void enqueue(PriorityQueue *pq, int vertex, int distance) {
    if (pq->size == V) {
        return;
    }
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->distance = distance;
    pq->data[pq->size] = newNode;
    upHeapify(pq, pq->size);
    pq->size++;
}

// 下沉操作
void downHeapify(PriorityQueue *pq, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < pq->size && pq->data[left]->distance < pq->data[smallest]->distance) {
        smallest = left;
    }

    if (right < pq->size && pq->data[right]->distance < pq->data[smallest]->distance) {
        smallest = right;
    }

    if (smallest!= index) {
        swap(&pq->data[index], &pq->data[smallest]);
        downHeapify(pq, smallest);
    }
}

// 移除并返回距离最小的节点
Node* dequeue(PriorityQueue *pq) {
    if (pq->size == 0) {
        return NULL;
    }
    Node *minNode = pq->data[0];
    pq->size--;
    pq->data[0] = pq->data[pq->size];
    downHeapify(pq, 0);
    return minNode;
}

// 释放优先队列内存
void freePriorityQueue(PriorityQueue *pq) {
    for (int i = 0; i < pq->size; i++) {
        free(pq->data[i]);
    }
}

// 找到距离数组中最小值的索引
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// 打印从源点到其他顶点的最短路径
void printPath(int parent[], int j) {
    if (parent[j] == -1) {
        printf("%d ", j);
        return;
    }
    printPath(parent, parent[j]);
    printf("%d ", j);
}

// 打印结果
void printSolution(int dist[], int parent[], int src) {
    printf("Vertex\t Distance\tPath\n");
    for (int i = 0; i < V; i++) {
        printf("%d -> %d\t\t %d\t\t%d ", src, i, dist[i], src);
        printPath(parent, i);
        printf("\n");
    }
}

// Dijkstra算法
void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int sptSet[V];
    int parent[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = 0;
        parent[i] = -1;
    }

    dist[src] = 0;

    PriorityQueue pq;
    initPriorityQueue(&pq);
    enqueue(&pq, src, 0);

    while (pq.size > 0) {
        Node *minNode = dequeue(&pq);
        int u = minNode->vertex;
        free(minNode);
        sptSet[u] = 1;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u]!= INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;
                enqueue(&pq, v, dist[v]);
            }
        }
    }

    printSolution(dist, parent, src);
    freePriorityQueue(&pq);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0,