做公司网站备案可以个人,物联网工程就业方向及前景,婴儿衣服做的网站,免费缩短网址文章目录 什么是优先队列#xff1f;堆排序代码实现408考研各数据结构C/C代码#xff08;Continually updating#xff09; 什么是优先队列#xff1f;
下面的内容来自于百度百科。 如果我们给每个元素都分配一个数字来标记其优先级#xff0c;不妨设较小的数字具有较高的… 文章目录 什么是优先队列堆排序代码实现408考研各数据结构C/C代码Continually updating 什么是优先队列
下面的内容来自于百度百科。 如果我们给每个元素都分配一个数字来标记其优先级不妨设较小的数字具有较高的优先级这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样我们就引入了优先级队列这种数据结构。 优先级队列priority queue 是0个或多个元素的集合每个元素都有一个优先权对优先级队列执行的操作有1查找2插入一个新元素 3删除 一般情况下查找操作用来搜索优先权最大的元素删除操作用来删除该元素 。对于优先权相同的元素可按先进先出次序处理或按任意优先权进行。 简而言之我们定义了一种数据结构这种数据结构在插入数据的时候会按照优先级进行排序从而使得每次取出的元素都会保证一定的顺序。 也就是说在我们插入数据之后会对当前数据结构进行一次排序。 在优先队列中每个元素都与一个优先级相关联这个优先级可以是一个数字、权重、时间戳或其他可以用来衡量元素重要性的值。
优先队列的主要特点是能够按照元素的优先级来进行插入、访问和删除操作确保高优先级的元素在处理时具有更高的优先级。这使得优先队列在以下情况下非常有用
任务调度在任务管理中不同的任务可能具有不同的紧急性或优先级。优先队列可用于选择下一个要执行的任务确保高优先级任务首先执行。 图算法在图算法中如Dijkstra算法和Prim算法需要选择具有最小权重的边或顶点。优先队列可用于高效地选择最小权重的元素。 事件模拟在事件驱动系统中事件具有不同的时间戳应按照时间戳的顺序来处理。优先队列可用于管理事件并确保按时间戳的顺序执行。 数据压缩在Huffman编码等数据压缩算法中优先队列可用于构建最优编码树以最小化压缩文件的大小。 资源分配在资源管理中资源可以按照优先级分配给不同的任务或请求以确保最重要的任务获得优先访问资源。 网络路由在网络路由中优先队列可用于选择最佳路径以最小化延迟或最大化带宽利用率。
在我开发代码的过程中优先队列最常用最常用的场景就是做一个任务调度系统来保证高优先级的任务都会较早被执行。
堆排序
如果了解堆排序的就会明白优先队列的实现原理和堆排序其实差不多。 堆排序在不断遍历堆的过程中会不断的将堆变成大顶堆或者小顶堆这很明显就符合我们对优先队列的要求。也就是每次堆顶都是高优先级的数据。 堆排序
代码实现
基于上面的特性优先队列可以用多种不同的数据结构来实现包括二叉堆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中各种常用的数据结构的代码并且希望我附上比较完整的注释以及提供用户输入功能okfine这个专栏会一直更新直到我认为没有新的数据结构可以讲解了。 目前我比较熟悉的数据结构如下 数组、链表、队列、栈、树、B/B树、红黑树、Hash、图。 所以我会先有空更新出如下几个数据结构的代码欢迎关注。 当然在我前两年的博客中对于链表、哈夫曼树等常用数据结构我都提供了比较完整的详细的实现以及思路讲解有兴趣可以去考古。
#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;
}
