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模擬實現的文章就介紹到這瞭,更多相關C++ priority_queue模擬實現內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!