温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C++中priority_queue如何实现

发布时间:2021-08-30 09:15:00 来源:亿速云 阅读:116 作者:小新 栏目:开发技术

小编给大家分享一下C++中priority_queue如何实现,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

    priority_queue概述

    priority_queue定义

    • 优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

    priority_queue特点

    • 优先队列是一种容器适配器,首先要包含头文件 #include<queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。

    • 优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。

    • 注意:默认情况下priority_queue是大根堆。如果想让其生成小根堆,需要使用到仿函数或者Lambda表达式。

    构造函数

    由于priority_queue是一种容器适配器,适配的是vector,我们在vector中已经写过它的构造函数了。故priority_queue在此不需要多余的其他构造函数。

    // 创造空的优先级队列
    priority_queue():m_priority_queue()
    {
    
    }
    
    template<class Iterator>
    priority_queue(Iterator first, Iterator last)
    	: m_priority_queue(first, last)
    {
    	// 将m_priority_queue中的元素调整成堆的结构
    	int count = m_priority_queue.size();
    	int root = ((count - 2) >> 1);
    	for (; root >= 0; root--)
    	AdjustDown(root);
    }

    修改相关函数

    push

    功能:push函数用来往堆中(尾部)插入一个元素,并向上调整成新的堆。

    //向上调整
    void AdjustUp(int child)
    {
    	int parent = (child-1)>>1;
    	
    	while (child > 0)
    	{
    		//其中c是一个对象,用该对象去调用仿函数来进行比较
    		if (c(m_priority_queue[parent], m_priority_queue[child]))
    		{
    			std::swap(m_priority_queue[parent], m_priority_queue[child]);
    			child = parent;
    			parent = (child - 1) >> 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    
    }
    
    void push(const T& val)
    {
    	m_priority_queue.push_back(val);
    	AdjustUp(m_priority_queue.size()-1);
    }

    pop

    功能:pop函数弹出堆顶元素。具体步骤是:堆顶元素与最后一个数字进行交换位置。之后在进行尾删来删除堆顶。再重新向下调堆。

    //向下调堆
    void AdjustDown(int parent)
    {
    	int child = (parent << 1) + 1;
    	int size = static_cast<int>(m_priority_queue.size());
    
    	while (child< size)
    	{
    		if (child + 1 < size && c(m_priority_queue[child],m_priority_queue[child + 1]) )
    		{
    			++child;
    		}
    
    		if (c(m_priority_queue[parent], m_priority_queue[child]))
    		{
    			std::swap(m_priority_queue[parent], m_priority_queue[child]);
    			parent = child;
    			child = (parent << 1) + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    void pop()
    {
    	assert(!m_priority_queue.empty());
    
    	std::swap(m_priority_queue[0], m_priority_queue[m_priority_queue.size()- 1]);
    	m_priority_queue.pop_back();
    	AdjustDown(0);
    }

    容量相关函数

    size

    功能:用来获取堆中的元素个数。

    size_t size()	const
    {
    	return m_priority_queue.size();
    }

    empty

    功能:用来判断堆中是否为空。

    bool empty()	const
    {
    	return m_priority_queue.empty();
    }

    元素访问相关函数

    top

    功能:用来获取堆顶的元素。

    T& top()
    {
    	return m_priority_queue.front();
    }
    
    const T& top()	const
    {
    	return m_priority_queue.front();
    }

    代码实现

    #pragma once
    #define _CRT_SECURE_NO_WARNINGS 1
    #include<iostream>
    #include<vector>
    #include<assert.h>
    namespace ZJ
    {
    	template<class T>
    	class less
    	{
    	public:
    		bool operator() (const T& x, const T& y) const
    		{
    			return x < y;
    		}
    	};
    
    	template<class T>
    	class greater
    	{
    	public:
    		bool operator() (const T& x, const T& y) const
    		{
    			return x > y;
    		}
    	};
    	template<class T,class Container=std::vector<T>, class Compare = ZJ::less<T>>
    	class priority_queue
    	{
    	public:
    		// 创造空的优先级队列
    		priority_queue():m_priority_queue()
    		{
    
    		}
    
    		template<class Iterator>
    		priority_queue(Iterator first, Iterator last)
    			: m_priority_queue(first, last)
    		{
    			// 将m_priority_queue中的元素调整成堆的结构
    			int count = m_priority_queue.size();
    			int root = ((count - 2) >> 1);
    			for (; root >= 0; root--)
    			AdjustDown(root);
    		}
    	public:
    
    		//向上调整
    		void AdjustUp(int child)
    		{
    			int parent = (child-1)>>1;
    			
    			while (child > 0)
    			{
    				if (c(m_priority_queue[parent], m_priority_queue[child]))
    				{
    					std::swap(m_priority_queue[parent], m_priority_queue[child]);
    					child = parent;
    					parent = (child - 1) >> 1;
    				}
    				else
    				{
    					break;
    				}
    			}
    
    		}
    		void push(const T& val)
    		{
    			m_priority_queue.push_back(val);
    			AdjustUp(m_priority_queue.size()-1);
    		}
    
    		void AdjustDown(int parent)
    		{
    			int child = (parent << 1) + 1;
    			int size = static_cast<int>(m_priority_queue.size());
    
    			while (child< size)
    			{
    				if (child + 1 < size && c(m_priority_queue[child],m_priority_queue[child + 1]) )
    				{
    					++child;
    				}
    
    				if (c(m_priority_queue[parent], m_priority_queue[child]))
    				{
    					std::swap(m_priority_queue[parent], m_priority_queue[child]);
    					parent = child;
    					child = (parent << 1) + 1;
    				}
    				else
    				{
    					break;
    				}
    			}
    		}
    
    		void pop()
    		{
    			assert(!m_priority_queue.empty());
    
    			std::swap(m_priority_queue[0], m_priority_queue[m_priority_queue.size()- 1]);
    			m_priority_queue.pop_back();
    			AdjustDown(0);
    		}
    
    		size_t size()	const
    		{
    			return m_priority_queue.size();
    		}
    
    		T& top()
    		{
    			return m_priority_queue.front();
    		}
    
    		const T& top()	const
    		{
    			return m_priority_queue.front();
    		}
    
    		bool empty()	const
    		{
    			return m_priority_queue.empty();
    		}
    
    	private:
    		Container m_priority_queue;
    		Compare c;
    	};
    }

    以上是“C++中priority_queue如何实现”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

    向AI问一下细节

    免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

    c++
    AI