模仿库实现priority

模仿库实现priority_queue

本文主要是介绍模仿库实现priority_queue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 priority_queue

1.1 概念

优先级队列，一种大/小堆(默认为大堆)

1.2 大堆和小堆

一种完全二叉树，大堆根节点一定比子字节大

小堆根节点一定比子字节小

向下调整

从根节点开始比较与子节点的大小不断向下

向上调整

找到最后一个非叶子节点，比较数值和父节点的大小，向上不断调整

1.3 框架说明

less和greater库中有，注释部分为模拟

不提供遍历所以不用写itreater

1.4 代码实现

namespace my_priority
{
//仿函数
//用类模仿函数
//通过重载括号实现
//template<class T>
//小堆
//struct less
//{
// bool operator()(T a,T b)
// {
// if (a < b)
// {
// return 1

// }
// else
// {
// return 0
// }
// }
//};
//template<class T>
//struct greater
//{
// bool operator()(T a, T b)
// {

// }
//};
//用Compare仿函数代替函数指针
template <class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
//构造
priority_queue()
:_size(0)
{}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: _size(0)
{
InputIterator it = first;
while (it != last)
{
this->push(*it);
}
}
//
bool empty() const;
size_t size() const;
//
T& top() const;
//
//向下调整

void push(const T& x)

{
//找最后一个非叶子节点
c.push_back(x);
up_adjust(c);//向上调整建堆
}
//
void pop();
//
private:
//容器
Container c;
//比较
Compare comp;
int _size;
//void down_adjust(Container& c)//向下调整
//{
// int child = 1;//左叶子
// int parent = 0;
// while (child < c.size())//子节点存在
// {
// //右叶子存在且比左叶子更小/大
// if (child + 1 < c.size() && comp(c[child], c[child + 1]))
// {
// child = child + 1;
// }
//
// if (comp(c[parent], c[child]))
// {
// swap(c[parent], c[child]);
// parent = child;
// child = child * 2;
// continue;
// }
// break;
// }
//}
void up_adjust(Container& c)//向上调整
{
int child = c.size() - 1;
int parent = child / 2;
while (comp(c[parent], c[child]))
{
swap(c[parent], c[child]);
child = parent;
parent = child / 2;
if (child == parent)
{
break;
}
}
}
};
};