C++——优先级队列(priority_queue)_c++priority_queue__好好学习的博客-CSDN博客
#include<iostream>
using namespace std;
#include<stack>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<queue>
struct cmp
{
bool operator()(int x, int y)
{
return x > y;//后面的优先级高,所以返回小顶堆,队头元素永远是最小的
}
};
int main()
{
priority_queue<int, vector<int>, cmp >pq;
pq.push(5);
pq.push(2);
pq.push(6);
pq.push(4);
while (!pq.empty())
{
cout << pq.top() << endl;//输出 2 4 5 6
pq.pop();
}
cout << "******" << endl;
priority_queue<int>pq1;输出 600 500 400 200
pq1.push(500);
pq1.push(200);
pq1.push(600);
pq1.push(400);
while (!pq1.empty())
{
cout << pq1.top() << endl;
pq1.pop();
}
system("pause");
return 0;
}
那么这道题就可以用小顶堆文章来源:https://www.toymoban.com/news/detail-686906.html
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
#include <queue>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param lists ListNode类vector
* @return ListNode类
*/
ListNode* mergeKLists(vector<ListNode*>& lists) {
// write code here
class MyCompare {
public:
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
priority_queue<ListNode*, vector<ListNode*>, MyCompare>pq;
for (int i = 0; i < lists.size(); i++) {
if (lists[i] != nullptr)
pq.push(lists[i]);
}
ListNode* res = new ListNode(0);
ListNode* cur = res;
ListNode* tmp = nullptr;
while (!pq.empty()) {
tmp = pq.top();
pq.pop();
cur->next = tmp;
cur = cur->next;
if (tmp->next != nullptr) {
pq.push(tmp->next);
}
}
return res->next;
}
};
分治的思想,归并排序的思想文章来源地址https://www.toymoban.com/news/detail-686906.html
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
//两个有序链表合并函数
//划分合并区间函数
ListNode* divideMerge(vector<ListNode *> &lists, int left, int right){
if(left == right)
return lists[left];
//从中间分成两段,再将合并好的两段合并
int mid = (left + right) / 2;
ListNode*pHead1=divideMerge(lists, left, mid);
ListNode*pHead2=divideMerge(lists, mid + 1, right);
//加一个表头
ListNode* head = new ListNode(0);
ListNode* cur = head;
//两个链表都要不为空
while(pHead1 && pHead2){
//取较小值的节点
if(pHead1->val <= pHead2->val){
cur->next = pHead1;
//只移动取值的指针
pHead1 = pHead1->next;
}else{
cur->next = pHead2;
//只移动取值的指针
pHead2 = pHead2->next;
}
//指针后移
cur = cur->next;
}
//哪个链表还有剩,直接连在后面
if(pHead1)
cur->next = pHead1;
else
cur->next = pHead2;
//返回值去掉表头
return head->next;
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
//k个链表归并排序
if(lists.size()==0)
return NULL;//样例有这种情况
return divideMerge(lists, 0, lists.size() - 1);
}
};
到了这里,关于合并 k 个升序的链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!