C++ queue

namespace byte
{
	template<class T, class Container = list<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_front();
		}

		const T& front()
		{
			return _con.front();
		}

		const T& back()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

	private:
		Container _con;
	};

	void test_queue()
	{
		queue<int> q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);

		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}
}

四、优先级队列

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• front()：返回容器中第一个元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

五、priority_queue使用

• priority_queue()/priority_queue(first, last) 构造一个空的优先级队列

• empty( ) 检测优先级队列是否为空，是返回true，否则返回 false

• top( ) 返回优先级队列中最大(最小元素)，即堆顶元素

• push(x) 在优先级队列中插入元素x
• pop() 删除优先级队列中最大(最小)元素，即堆顶元素

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 构造一个空的优先级队列
    priority_queue<int> pq;

    // 检测优先级队列是否为空
    if (pq.empty()) {
        cout << "优先级队列为空" << endl;
    } else {
        cout << "优先级队列不为空" << endl;
    }

    // 使用迭代器范围构造优先级队列
    vector<int> nums = {3, 1, 4, 1, 5, 9};
    priority_queue<int> pq2(nums.begin(), nums.end());

    // 输出堆顶元素
    cout << "堆顶元素为: " << pq2.top() << endl;

    // 在优先级队列中插入元素
    pq2.push(2);
    pq2.push(7);

    // 输出堆顶元素
    cout << "堆顶元素为: " << pq2.top() << endl;

    // 删除堆顶元素
    pq2.pop();

    // 输出堆顶元素
    cout << "堆顶元素为: " << pq2.top() << endl;

    return 0;
}

OJ题：215.?数组中的第K个最大元素

快速排序

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

优先级队列

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(),nums.end());
        while(--k){
            pq.pop();
        }
        return pq.top();
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);
        for(size_t i=k;i<nums.size();i++){
            if(nums[i]>pq.top()){
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};

六、模拟实现priority_queue

1、仿函数

?在C++中，仿函数（Functor）是一种重载了函数调用操作符?operator()?的对象。它实际上是一个类或者结构体，通过重载?operator()，使得该对象可以像函数一样被调用。仿函数可以像函数一样接受参数，并返回结果，同时可以包含状态信息，因此它们在C++中被广泛用于实现函数对象，作为算法的参数传递，或者用于定义自定义的操作。

#pragma once
#include <vector>
using namespace std;

namespace hhh
{
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

使用仿函数的好处是可以将特定的操作封装为一个对象，使得代码更加灵活和可扩展。通过重载函数调用操作符，可以将对象当作函数来使用，这样可以方便地在算法或数据结构中使用。在这个实现中，less?和?greater?结构体被用作仿函数，用于定义元素的比较方式。less?结构体表示小的元素优先级高，greater?结构体表示大的元素优先级高。

2、优先级队列类

	template<class T, class Container = vector<T>,class Compare=less<T>>
	class priority_queue 
    {
	private:
		Container _con;
    
    public:
		void adjust_up(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0){
				if(com(_con[parent],_con[child])){
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}

		void adjust_down(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < _con.size()) {
				Compare com;

				if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {
					++child;
				}
				if (com(_con[parent], _con[child])){
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}

		const T& top()
		{
			return _con[0];
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
    };
}

1. priority_queue?类：这是一个模板类，可以用于任何类型的元素。它有三个模板参数，T?是元素的类型，Container?是用于存储元素的容器类型，默认是?vector，Compare?是元素的比较方式，默认是?less。

2. adjust_up?函数：这个函数用于调整堆的结构，使得父节点的值大于或小于所有子节点的值。它的参数是一个子节点的索引，它会不断地将这个节点和它的父节点进行比较，如果父节点的值小于子节点的值，就交换这两个节点。

3. adjust_down?函数：这个函数也是用于调整堆的结构，它的参数是一个父节点的索引，它会不断地将这个节点和它的子节点进行比较，如果父节点的值小于任何一个子节点的值，就交换这两个节点。

4. push?函数：这个函数用于向优先级队列中添加一个元素。它首先将元素添加到向量的末尾，然后调用?adjust_up?函数来调整堆的结构。

5. pop?函数：这个函数用于从优先级队列中删除最大或最小的元素。它首先交换向量的第一个元素和最后一个元素，然后删除最后一个元素，最后调用?adjust_down?函数来调整堆的结构。

6. top?函数：这个函数用于获取优先级队列中最大或最小的元素。

7. size?和?empty?函数：这两个函数用于获取优先级队列中元素的数量和判断优先级队列是否为空。

3、测试函数

void test_priority_queue()
{

	// 默认是大堆
	priority_queue<int> pq;

	// 小堆
	//priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(1);
	pq.push(0);
	pq.push(5);
	pq.push(2);
	pq.push(1);
	pq.push(7);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

大堆：

小堆：