小梦C嘎嘎——启航篇】C++ priority_queue 手撕模拟实现😎
😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
前言🙌
哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘 都是精华内容，可不要错过哟！！！😍😍😍
priority_queue 简述
priority_queue 底层实现的数据结构是vector。其插入和删除逻辑实现上，运用了heap的实现思想。
下面这张图是有关其模板参数类型的介绍，以及对于这个数据结构的简单介绍。
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元
素)。 - 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
- 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指
定容器类，则使用vector。 - 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数
make_heap、push_heap和pop_heap来自动完成此操作 - 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
代器访问
priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
例题使用
思路分享：利用优先级队列默认是大堆的特性，将元素都放进优先级队列中，再将其前k- 1个元素删除，则第一个元素取到的就是第k大的元素。
代码分享：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int,vector<int>> q1(nums.begin(),nums.end());
while(--k)
{
q1.pop();
}
return q1.top();
}
};
priority_queue 简单模拟实现代码分享
#pragma once
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
namespace tai
{
template<class T>
struct less {
bool operator()(const T& a,const T& b)
{
return a < b;
}
};
template<class T>
struct greater {
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
//less 大堆 <
template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
public:
priority_queue()
{}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:c(first,last)
{
for (int i = (c.size() - 2) / 2; i >= 0; i++)
{
adjust_down(i);
}
}
bool empty() const
{
return c.empty();
}
size_t size() const
{
return c.size();
}
const T& top() const
{
return c[0];
}
void adjust_up(int child)
{
int father = (child - 1) / 2;
while (child > 0)
{
//if (c[child] > c[father])
//if (c[father] < c[child])
if(comp(c[father], c[child]))
{
swap(c[child], c[father]);
child = father;
father = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(int father)
{
int child = father * 2 + 1;
while (child < c.size())
{
//先选出比较大的那个孩子
if (child + 1 < c.size() && comp(c[child], c[child + 1]))
{
child++;
}
//if (comp.operator()(c[father], c[child]))
if(comp(c[father], c[child]))
{
swap(c[child], c[father]);
father = child;
child = 2 * father + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
c.push_back(x);//先插入
//向上调整建堆
adjust_up(c.size() - 1);
}
void pop()
{
swap(c[0], c[c.size() - 1]);
c.pop_back();
//向下调整
adjust_down(0);
}
private:
Container c;
Compare comp;
};
};
总结撒花💞
本篇文章旨在分享的是优先级队列（priority_queue）的C++语言模拟实现和使用分享。希望大家通过阅读此文有所收获！
😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘
