C++中priority_queue如何實(shí)現(xiàn)

小編給大家分享一下C++中priority_queue如何實(shí)現(xiàn)，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

priority_queue概述

priority_queue定義

• 優(yōu)先級(jí)隊(duì)列是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。
  

priority_queue特點(diǎn)

• 優(yōu)先隊(duì)列是一種容器適配器，首先要包含頭文件 #include<queue>, 他和queue不同的就在于我們可以自定義其中數(shù)據(jù)的優(yōu)先級(jí), 讓優(yōu)先級(jí)高的排在隊(duì)列前面,優(yōu)先出隊(duì)。

• 優(yōu)先級(jí)隊(duì)列默認(rèn)使用vector作為其底層存儲(chǔ)數(shù)據(jù)的容器，在vector上又使用了堆算法將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。

• 注意：默認(rèn)情況下priority_queue是大根堆。如果想讓其生成小根堆，需要使用到仿函數(shù)或者Lambda表達(dá)式。
  

構(gòu)造函數(shù)

由于priority_queue是一種容器適配器，適配的是vector,我們?cè)趘ector中已經(jīng)寫過它的構(gòu)造函數(shù)了。故priority_queue在此不需要多余的其他構(gòu)造函數(shù)。

// 創(chuàng)造空的優(yōu)先級(jí)隊(duì)列
priority_queue():m_priority_queue()
{

}

template<class Iterator>
priority_queue(Iterator first, Iterator last)
	: m_priority_queue(first, last)
{
	// 將m_priority_queue中的元素調(diào)整成堆的結(jié)構(gòu)
	int count = m_priority_queue.size();
	int root = ((count - 2) >> 1);
	for (; root >= 0; root--)
	AdjustDown(root);
}

修改相關(guān)函數(shù)

push

功能：push函數(shù)用來往堆中(尾部)插入一個(gè)元素，并向上調(diào)整成新的堆。

//向上調(diào)整
void AdjustUp(int child)
{
	int parent = (child-1)>>1;
	
	while (child > 0)
	{
		//其中c是一個(gè)對(duì)象，用該對(duì)象去調(diào)用仿函數(shù)來進(jìn)行比較
		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函數(shù)彈出堆頂元素。具體步驟是：堆頂元素與最后一個(gè)數(shù)字進(jìn)行交換位置。之后在進(jìn)行尾刪來刪除堆頂。再重新向下調(diào)堆。

//向下調(diào)堆
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);
}

容量相關(guān)函數(shù)

size

功能：用來獲取堆中的元素個(gè)數(shù)。

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

empty

功能：用來判斷堆中是否為空。

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

元素訪問相關(guān)函數(shù)

top

功能：用來獲取堆頂?shù)脑亍?/p>

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

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

代碼實(shí)現(xiàn)

#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:
		// 創(chuàng)造空的優(yōu)先級(jí)隊(duì)列
		priority_queue():m_priority_queue()
		{

		}

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: m_priority_queue(first, last)
		{
			// 將m_priority_queue中的元素調(diào)整成堆的結(jié)構(gòu)
			int count = m_priority_queue.size();
			int root = ((count - 2) >> 1);
			for (; root >= 0; root--)
			AdjustDown(root);
		}
	public:

		//向上調(diào)整
		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如何實(shí)現(xiàn)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！