C++中priority_queue模擬實(shí)現(xiàn)的代碼示例
更新時間：2021年08月29日 10:35:50 作者：可樂不解渴
在c++語言中數(shù)據(jù)結(jié)構(gòu)中的堆結(jié)構(gòu)可以通過STL庫中的priority_queue 優(yōu)先隊列來實(shí)現(xiàn),這樣做極大地簡化了我們的工作量,這篇文章主要給大家介紹了關(guān)于C++中priority_queue模擬實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下
priority_queue概述
priority_queue定義
- 優(yōu)先級隊列是不同于先進(jìn)先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素。
priority_queue特點(diǎn)
- 優(yōu)先隊列是一種容器適配器，首先要包含頭文件 #include<queue>, 他和queue不同的就在于我們可以自定義其中數(shù)據(jù)的優(yōu)先級, 讓優(yōu)先級高的排在隊列前面,優(yōu)先出隊。
- 優(yōu)先級隊列默認(rèn)使用vector作為其底層存儲數(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,我們在vector中已經(jīng)寫過它的構(gòu)造函數(shù)了。故priority_queue在此不需要多余的其他構(gòu)造函數(shù)。
// 創(chuàng)造空的優(yōu)先級隊列
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ù)用來往堆中(尾部)插入一個元素，并向上調(diào)整成新的堆。
//向上調(diào)整
void AdjustUp(int child)
{
int parent = (child-1)>>1;
while (child > 0)
{
//其中c是一個對象，用該對象去調(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ù)彈出堆頂元素。具體步驟是：堆頂元素與最后一個數(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
功能：用來獲取堆中的元素個數(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)先級隊列
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;
};
}
總結(jié)
到此這篇關(guān)于C++中priority_queue模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ priority_queue模擬實(shí)現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++ map 根據(jù)value找key的實(shí)現(xiàn)
今天小編就為大家分享一篇C++ map 根據(jù)value找key的實(shí)現(xiàn)，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
opencv3/C++ 實(shí)現(xiàn)SURF特征檢測
今天小編就為大家分享一篇opencv3/C++ 實(shí)現(xiàn)SURF特征檢測，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
基于C++實(shí)現(xiàn)俄羅斯方塊游戲的示例代碼
俄羅斯方塊（Tetris）是一款風(fēng)靡全球的經(jīng)典益智游戲,自1984年首次發(fā)布以來,便吸引了無數(shù)玩家,在這篇博文中,我們將深入探討如何用 C++ 編寫一個簡單的俄羅斯方塊游戲,我們將從游戲的基本概念和設(shè)計入手,逐步實(shí)現(xiàn)游戲的各個功能模塊,感興趣小伙伴快來看看吧2024-11-11
在本篇文章里小編給大家整理的是關(guān)于c語言如何求余數(shù)的相關(guān)知識點(diǎn)內(nèi)容，有需要的朋友們可以學(xué)習(xí)下。2020-02-02
Dijkstra（迪杰斯特拉）算法是典型的最短路徑路由算法，用于計算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。下面這篇文章就給大家介紹關(guān)于C++用Dijkstra算法(迪杰斯特拉算法)求最短路徑的方法，下面來一起看看吧。2016-12-12
使用Qt/C++實(shí)現(xiàn)WGS84,高德GCJ-02與百度BD-09坐標(biāo)系間相互轉(zhuǎn)化
這篇文章主要為大家詳細(xì)介紹了如何使用Qt實(shí)現(xiàn)WGS84、高德GCJ-02與百度BD-09坐標(biāo)系間相互轉(zhuǎn)化，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-07-07
這篇文章主要為大家詳細(xì)介紹了C++如何獲取本機(jī)IP地址小程序，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要為大家詳細(xì)介紹了語言C的動態(tài)內(nèi)存管理，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要介紹了C++模板顯式具體化，在C++中，可以提供一個具體化函數(shù)定義稱為具體顯式化（explict?specialization）。其中包含所需的代碼，當(dāng)編譯器找到與函數(shù)調(diào)用匹配的具體化定義時，將使用該定義，而不再尋找模板，下面我們來看看文章具體介紹吧2021-12-12
關(guān)鍵字，這名字一聽，就很關(guān)鍵。而有些關(guān)鍵字，你可能不是很了解，更別談使用。所以，這篇文章將帶你見識常見的關(guān)鍵字，一起領(lǐng)略它們的風(fēng)采吧2022-10-10