【数据结构C/C++】优先（级）队列

淩亂°似流年 2024-02-21 07:38 42阅读 0赞

#### 文章目录 ####

*  什么是优先队列？
 *  堆排序
 *  代码实现
 *  408考研各数据结构C/C++代码（Continually updating）

## 什么是优先队列？ ##

下面的内容来自于百度百科。

> 如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列这种数据结构。 优先级队列（priority queue）  
> 是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有（1）查找（2）插入一个新元素 （3）删除  
> 一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素 。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

简而言之，我们定义了一种数据结构，这种数据结构在插入数据的时候会按照优先级进行排序，从而使得每次取出的元素都会保证一定的顺序。  
也就是说，在我们插入数据之后，会对当前数据结构进行一次排序。  
在优先队列中，每个元素都与一个优先级相关联，这个优先级可以是一个数字、权重、时间戳或其他可以用来衡量元素重要性的值。

优先队列的主要特点是能够按照元素的优先级来进行插入、访问和删除操作，确保高优先级的元素在处理时具有更高的优先级。这使得优先队列在以下情况下非常有用：

任务调度：在任务管理中，不同的任务可能具有不同的紧急性或优先级。优先队列可用于选择下一个要执行的任务，确保高优先级任务首先执行。  
图算法：在图算法中，如Dijkstra算法和Prim算法，需要选择具有最小权重的边或顶点。优先队列可用于高效地选择最小权重的元素。  
事件模拟：在事件驱动系统中，事件具有不同的时间戳，应按照时间戳的顺序来处理。优先队列可用于管理事件并确保按时间戳的顺序执行。  
数据压缩：在Huffman编码等数据压缩算法中，优先队列可用于构建最优编码树，以最小化压缩文件的大小。  
资源分配：在资源管理中，资源可以按照优先级分配给不同的任务或请求，以确保最重要的任务获得优先访问资源。  
网络路由：在网络路由中，优先队列可用于选择最佳路径，以最小化延迟或最大化带宽利用率。

在我开发代码的过程中，优先队列最常用最常用的场景就是做一个任务调度系统，来保证高优先级的任务都会较早被执行。

## 堆排序 ##

如果了解堆排序的，就会明白，优先队列的实现原理和堆排序其实差不多。  
堆排序在不断遍历堆的过程中会不断的将堆变成大顶堆或者小顶堆，这很明显就符合我们对优先队列的要求。也就是每次堆顶都是高优先级的数据。  
[堆排序][Link 1]

## 代码实现 ##

基于上面的特性，优先队列可以用多种不同的数据结构来实现，包括二叉堆（Binary Heap）、斐波那契堆（Fibonacci Heap）、二项堆（Binomial Heap）、左偏树（Leftist Tree）等。每种实现方式都有其优点和缺点，适用于不同类型的问题。  
对于优先队列，我们可以选择支持动态扩展容量，也可以选择固定容量，在容量过大后不允许插入新元素。具体选择那种方式看你的业务需求。  
这里我们就掌握常用的基于堆的方式实现的优先队列。代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    // 结构体表示小顶堆
    typedef struct PriorityQueue {
        
        int* heap;
        int capacity;
        int size;
    } PriorityQueue;
    
    // 创建小顶堆，初始化容量
    PriorityQueue* createPriorityQueue(int capacity) {
        
        PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
        pq->capacity = capacity;
        pq->size = 0;
        pq->heap = (int*)malloc(capacity * sizeof(int));
        return pq;
    }
    
    // 交换两个整数的值
    void swap(int* a, int* b) {
        
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    // 向小顶堆中插入元素
    void offer(PriorityQueue* pq, int element) {
        
        if (pq->size == pq->capacity) {
        
            // 队列已满，需要扩展
            pq->capacity *= 2;
            pq->heap = (int*)realloc(pq->heap, pq->capacity * sizeof(int));
        }
    
        int currentIndex = pq->size;
        pq->heap[currentIndex] = element;
    
        while (currentIndex > 0) {
        
            int parentIndex = (currentIndex - 1) / 2;
            if (pq->heap[currentIndex] >= pq->heap[parentIndex]) {
        
                break;
            }
            swap(&pq->heap[currentIndex], &pq->heap[parentIndex]);
            currentIndex = parentIndex;
        }
    
        pq->size++;
    }
    
    // 从小顶堆中移除并返回最小值
    int poll(PriorityQueue* pq) {
        
        if (pq->size == 0) {
        
            // 队列为空
            exit(1); // 或者返回一个错误值，具体情况而定
        }
    
        int min = pq->heap[0];
        int last = pq->heap[pq->size - 1];
        pq->size--;
    
        if (pq->size > 0) {
        
            pq->heap[0] = last;
            int currentIndex = 0;
    
            while (1) {
        
                int leftChildIndex = 2 * currentIndex + 1;
                int rightChildIndex = 2 * currentIndex + 2;
                int smallest = currentIndex;
    
                if (leftChildIndex < pq->size && pq->heap[leftChildIndex] < pq->heap[smallest]) {
        
                    smallest = leftChildIndex;
                }
    
                if (rightChildIndex < pq->size && pq->heap[rightChildIndex] < pq->heap[smallest]) {
        
                    smallest = rightChildIndex;
                }
    
                if (smallest == currentIndex) {
        
                    break;
                }
    
                swap(&pq->heap[currentIndex], &pq->heap[smallest]);
                currentIndex = smallest;
            }
        }
    
        return min;
    }
    
    // 返回小顶堆中的最小值，不移除
    int peek(PriorityQueue* pq) {
        
        if (pq->size == 0) {
        
            // 队列为空
            exit(1); // 或者返回一个错误值，具体情况而定
        }
        return pq->heap[0];
    }
    
    // 检查小顶堆是否为空
    int isEmpty(PriorityQueue* pq) {
        
        return pq->size == 0;
    }
    
    // 返回小顶堆的大小
    int size(PriorityQueue* pq) {
        
        return pq->size;
    }
    
    // 销毁小顶堆并释放内存
    void destroyPriorityQueue(PriorityQueue* pq) {
        
        free(pq->heap);
        free(pq);
    }
    
    int main() {
        
        int capacity = 10;
        PriorityQueue* minHeap = createPriorityQueue(capacity);
    
        int userInput;
        printf("输入元素（输入-1结束）:\n");
    
        while (1) {
        
            scanf("%d", &userInput);
            if (userInput == -1) {
        
                break;
            }
            offer(minHeap, userInput);
        }
    
        printf("大小: %d\n", size(minHeap));
        printf("堆顶元素: %d\n", peek(minHeap));
    
        printf("出堆并打印元素:\n");
        while (!isEmpty(minHeap)) {
        
            printf("%d ", poll(minHeap));
        }
        printf("\n");
    
        destroyPriorityQueue(minHeap);
        return 0;
    }

## 408考研各数据结构C/C++代码（Continually updating） ##

[ 408考研各数据结构C/C++代码（Continually updating）][408_C_C_Continually updating]  
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。  
目前我比较熟悉的数据结构如下：  
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。  
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。

[Link 1]: https://blog.csdn.net/Zhangsama1/article/details/133840046?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22133840046%22,%22source%22:%22Zhangsama1%22%7D
[408_C_C_Continually updating]: https://blog.csdn.net/Zhangsama1/article/details/133676491?spm=1001.2014.3001.5502