asp网站开发的实训,itc会议系统,免费个人网站模版下载,wordpress用户发表文章特定目录优先队列是计算机科学中的一种抽象数据类型#xff0c;它是一种队列#xff1a;元素拥有优先级#xff0c;优先级最高的元素最先得到服务#xff1b;优先级相同的元素按照在集合中的顺序得到服务。优先队列有两种主要的实现方法#xff1a;堆和二叉搜索树。
简单来说它是一种队列元素拥有优先级优先级最高的元素最先得到服务优先级相同的元素按照在集合中的顺序得到服务。优先队列有两种主要的实现方法堆和二叉搜索树。
简单来说优先队列是一种特殊的队列不同于先进先出的普通队列优先队列中的每个元素都有一定的优先级优先级最高的元素最先出队。故而优先队列非常适合用来解决一些涉及元素优先级的问题。
在C的STL中priority_queue是实现优先队列的一个类模板。priority_queue中的元素默认按照大顶堆的方式进行排列即出队顺序是优先级由高到低。
下面我们来介绍三个使用优先队列解决的典型问题
1. 第K大元素查询
给定一个未排序的数组找出第K大的元素。例如给定数组[3,2,1,5,6,4]和k 2返回5.
代码实现及注释:
#include queue
#include vector
#include iostream
using namespace std;int findKthLargest(vectorint nums, int k) {// 创建一个小顶堆当堆的大小超过k时弹出堆顶元素priority_queueint, vectorint, greaterint pq;for (int num : nums) {pq.push(num);if (pq.size() k) {pq.pop();}}// 当所有元素都已入堆后堆顶元素就是数组中第k大的元素return pq.top();
}int main() {vectorint nums {3,2,1,5,6,4};int k 2;cout The Kth largest number is: findKthLargest(nums, k) endl;return 0;
}2. 合并K个排序链表
给定K个已排序的链表将它们合并为一个新的排序链表。
代码实现及注释:
#include queue
#include vector
#include iostream
using namespace std;struct ListNode {int val;ListNode *next;ListNode() : val(0), next(NULL) {}
};struct compare {bool operator()(ListNode* l1, ListNode* l2) {return l1-val l2-val;}
};ListNode* mergeKLists(vectorListNode* lists) {// 创建一个小顶堆把所有链表的头节点放入堆中priority_queueListNode*, vectorListNode*, compare pq;for (ListNode* list : lists) {if (list) {pq.push(list);}}ListNode *dummy new ListNode();ListNode *cur dummy;while (!pq.empty()) {// 取出当前最小的节点存入新链表中ListNode* node pq.top(); pq.pop();cur-next node;cur node;if (node-next) {pq.push(node-next); // 将当前最小节点的后续节点放入优先队列中}}return dummy-next; // 返回去掉哑节点头的链表
}3. 数据流的中位数
给定一个数据流寻找数据流的中位数。例如数据流[2,3,4]的中位数是3数据流[2,3]的中位数是2.5.
代码实现及注释:
#include queue
using namespace std;class MedianFinder {
public:/** initialize your data structure here. */MedianFinder() {}void addNum(int num) {left.push(num);right.push(-left.top());left.pop();if (left.size() right.size()) {left.push(-right.top());right.pop();}}double findMedian() {if (left.size() right.size()) {return left.top();} else {return (left.top() - right.top()) / 2.0;}}private:// 左侧大顶堆右侧小顶堆保证大顶堆的所有元素都小于小顶堆且大顶堆的元素可以多一个priority_queueint left;priority_queueint right;
};这三个案例展示了优先队列在不同问题中的应用包括寻找第K大元素合并排序链表以及寻找数据流的中位数。请记住优先队列主要用于处理涉及元素优先级的问题。
如果你想更深入地了解人工智能的其他方面比如机器学习、深度学习、自然语言处理等等也可以点击这个链接我按照如下图所示的学习路线为大家整理了100多G的学习资源基本涵盖了人工智能学习的所有内容包括了目前人工智能领域最新顶会论文合集和丰富详细的项目实战资料可以帮助你入门和进阶。
链接 人工智能交流群大量资料
