C++中priority_queue模拟实现的代码示例

在c++语言中数据结构中的堆结构可以通过STL库中的priority_queue优先队列来实现,这样做极大地简化了我们的工作量,这篇文章主要给大家介绍了关于C++中priority_queue模拟实现的相关资料,需要的朋友可以参考下

C++priority_queue模拟实现的代码示例,久久派带你了解更多相关信息。

目录
  • priority_queue概述
    • priority_queue定义
    • priority_queue特点
  • 构造函数
    • 修改相关函数
      • push
      • pop
    • 容量相关函数
      • size
      • empty
    • 元素访问相关函数
      • top
    • 总结

      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模拟实现的文章就介绍到这了,更多相关C++ priority_queue模拟实现内容请搜索趣讯吧以前的文章或继续浏览下面的相关文章希望大家以后多多支持趣讯吧!

      版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件至 203304862@qq.com 举报,一经查实,本站将立刻删除。转转请注明出处:https://www.szhjjp.com/n/18620.html

      发表评论

      您的电子邮箱地址不会被公开。 必填项已用*标注