【C++】priority_queue和deque的使用与实现

#include <iostream>
#include <vector>
#include <queue>
#include <functional>   // greater算法的头文件
using namespace std;

void test1()
{
	// 默认情况下，创建的是大堆，其底层按照小于比较
	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1;
	for (auto& e : v)
		q1.push(e);
	cout << q1.top() << endl;

	// 如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	cout << q2.top() << endl;
}

int main()
{
	test1();
	return 0;
}

class Date
{
	friend ostream& operator<<(ostream& _cout, const Date& d);

public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}

	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}

	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}

private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}

void test2()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2018, 10, 29));
	q1.push(Date(2018, 10, 28));
	q1.push(Date(2018, 10, 30));
	cout << q1.top() << endl;

	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2018, 10, 29));
	q2.push(Date(2018, 10, 28));
	q2.push(Date(2018, 10, 30));
	cout << q2.top() << endl;
}

int main()
{
	test2();

	return 0;
}

#pragma once
#include<vector>

// 优先队列模板类
// T: 元素类型, Container: 底层容器类型(默认vector), Compare: 比较器类型(默认less<T>)
template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
public:
    // 默认构造函数
    priority_queue() {}

    // 向下调整算法(堆化)
    // 用于维护堆性质，当某个节点不满足堆性质时，将其向下调整
    // a: 容器引用, n: 堆的大小, root: 要调整的根节点下标
    void AdjustDown(Container& a, int n, int root)
    {
        int parent = root;
        int child = parent * 2 + 1; // 左孩子
        
        while (child < n)
        {
            // 如果右孩子存在且比左孩子大(对于大堆)，选择较大的孩子
            if (child + 1 < n && _comp(a[child], a[child + 1]))
            {
                ++child; // 选择右孩子
            }
            
            // 如果父节点小于孩子节点(对于大堆)，需要交换
            if (_comp(a[parent], a[child]))
            {
                swap(a[child], a[parent]);
                parent = child;          // 继续向下调整
                child = parent * 2 + 1;  // 新的左孩子
            }
            else
            {
                break; // 已经满足堆性质，退出循环
            }
        }
    }

    // 向上调整算法
    // 用于在插入新元素后维护堆性质，从叶子节点向上调整
    // child: 新插入元素的下标
    void AdjustUp(int child)
    {
        Compare com;
        int parent = (child - 1) / 2; // 计算父节点下标
        
        while (child > 0)
        {
            // 如果父节点小于孩子节点(对于大堆)，需要交换
            //if (_c[parent] < _c[child])
            if (com(_c[parent], _c[child]))
            {
                swap(_c[child], _c[parent]);
                child = parent;           // 继续向上调整
                parent = (child - 1) / 2; // 新的父节点
            }
            else
            {
                break; // 已经满足堆性质，退出循环
            }
        }
    }

    // 使用迭代器范围构造优先队列
    // first: 起始迭代器, last: 结束迭代器
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
        :_c(first, last) // 用迭代器范围初始化底层容器
    {
        int size = _c.size();
        // 从最后一个非叶子节点开始，向前逐个向下调整建堆
        int i = (size - 2) / 2; // 最后一个非叶子节点的下标
        
        while (i >= 0)
        {
            AdjustDown(_c, last - first, i);
            i--;
        }
    }
    
    // 判断优先队列是否为空
    bool empty() const
    {
        return _c.empty();
    }
    
    // 返回优先队列中元素个数
    size_t size() const
    {
        return _c.size();
    }
    
    // 返回堆顶元素(非const版本)
    T& top()
    {
        return _c[0]; // 堆顶元素总是在容器首部
    }
    
    // 返回堆顶元素(const版本)
    const T& top()const
    {
        return _c[0];
    }
    
    // 插入新元素
    void push(const T& x)
    {
        _c.push_back(x);        // 在尾部插入新元素
        AdjustUp(_c.size() - 1); // 从新插入的位置向上调整
    }
    
    // 删除堆顶元素
    void pop()
    {
        swap(_c[0], _c[_c.size() - 1]); // 将堆顶元素与最后一个元素交换
        _c.pop_back();                   // 删除原来的堆顶元素(现在在尾部)
        AdjustDown(_c, _c.size(), 0);    // 从新的堆顶位置向下调整
    }
    
private:
    Container _c;     // 底层容器，用于存储堆元素
    Compare _comp;    // 比较器对象，用于元素比较
};

#include<deque>
template<class T, class Con = deque<T>>
class stack
{
public:
    stack()
    {
    }
    void push(const T& x)
    {
        _c.push_back(x);
    }
    void pop()
    {
        _c.pop_back();
    }
    T& top()
    {
        return _c.back();
    }
    const T& top()const
    {
        return _c.back();
    }
    size_t size()const
    {
        return _c.size();
    }
    bool empty()const
    {
        return _c.empty();
    }
private:
    Con _c;
};

#include<deque>
template<class T, class Con = deque<T>>
class queue
{
public:
    queue()
    {
    }
    void push(const T& x)
    {
        _c.push_back(x);
    }
    void pop()
    {
        _c.pop_front();
    }
    T& back()
    {
        return _c.back();
    }
    const T& back()const
    {
        return _c.back();
    }
    T& front()
    {
        return _c.front();
    }
    const T& front()const
    {
        return _c.front();
    }
    size_t size()const
    {
        return _c.size();
    }
    bool empty()const
    {
        return _c.empty();
    }
private:
    Con _c;
};