2021-1 索引优先队列 c++

原理

• 背景：常见的，用例已经有了N个元素，且有多个平行数组。只需要把索引加入队列。如果有现成的结构体数组，只要一个关于索引的优先队列即可。
• 注意到，只调整索引（一个整型数）要比交换结构体高效很多。
• 索引优先队列，可理解为能够快速访问最小元素的数组（甚至是任意一部分子集的最小元素，只把这一部分加入队列就好）。

API

实现

#pragma once
#include<string>
#include<iostream>
#include<vector>
using namespace std;#define out(x) cout<<x<<" "
#define hh cout<<endltemplate<class Key>
class IndexMinPQ
{
    
public:IndexMinPQ(int maxN);//functionsbool empty() {
     return m_N == 0; }int size() {
     return m_N; }bool contains(int k) {
     return (*m_qp)[k] != -1; }int minIndex() {
     return m_pq[1]; }Key keyOf(int k) {
     return m_keys->at(k); }Key min();int delMin();void change(int k, Key key);void insert(int i, Key key);void remove(int k);
private:int m_maxN = 0;int m_N = 0;vector<int>* m_pq = nullptr;//保存索引，二叉堆，从一开始vector<int>* m_qp = nullptr;//逆序，qp[pq[i]]=pq[qp[i]]=ivector<Key>* m_keys = nullptr;//保存元素void sink(int k);//下沉void swim(int k);//上浮bool less(int x, int y);//y是否小于xvoid exch(int x, int y);bool greater(int i, int j);//x是否大于yvoid validateIndex(int idx);
};void test_IndexMinPQ();

#include "IndexMinPQ.h"template<class Key>
inline IndexMinPQ<Key>::IndexMinPQ(int maxN)
{
    if (maxN < 0) {
    out("maxN needs >0.\n");return;}m_maxN = maxN;m_N = 0;//队列中元素个数m_keys = new vector<Key>(maxN + 1);m_pq = new vector<int>(maxN + 1);m_qp = new vector<int>(maxN + 1);//不要0位置for (int i = 1; i <= maxN; ++i){
    m_qp->at(i) = -1;}}template<class Key>
void IndexMinPQ<Key>::insert(int i, Key key)
{
    if (contains(i)) {
    out("index is already in the priority queue.");return;}m_N++;//加到末尾，并上浮m_qp->at(i) = m_N;m_pq->at(m_N) = i;m_keys->at(i) = key;swim(m_N);
}template<class Key>
Key IndexMinPQ<Key>::min()
{
    int min_i = m_pq->at(1);return m_keys->at(min_i);
}template<class Key>
int IndexMinPQ<Key>::delMin()
{
    if (m_N == 0) {
    out("priority queue underflow.");return -1;}int min = m_pq->at(1);exch(1, m_N--);sink(1);//assert(min == m_pq[m_N + 1]);m_qp->at(min) = -1;m_keys->at(min) = Key();m_pq->at(m_N + 1) = -1;return min;
}template<class Key>
void IndexMinPQ<Key>::change(int i, Key key)
{
    validateIndex(i);if (!contains(i)) {
    out("index is not in priority queue.");return;}m_keys->at(i) = key;swim(m_qp->at(i));sink(m_qp->at(i));
}template<class Key>
void IndexMinPQ<Key>::sink(int k)
{
    while (k * 2 <= m_N) {
    int j = 2 * k;if (j < m_N && less(j, j + 1)) j++;if (!less(k, j)) break;exch(k, j);k = j;}
}template<class Key>
void IndexMinPQ<Key>::swim(int k)
{
    while (k > 1 && less(k / 2, k)) {
    exch(k, k / 2);k = k / 2;}
}template<class Key>
void IndexMinPQ<Key>::exch(int x, int y)
{
    Key swap_ = m_pq->at(x);m_pq->at(x) = m_pq->at(y);m_pq->at(y) = swap_;//调整完后，更新qpm_qp->at(m_pq->at(x)) = x;m_qp->at(m_pq->at(y)) = y;
}template<class Key>
bool IndexMinPQ<Key>::greater(int i, int j)
{
    //优先队列存索引i = m_pq->at(i);j = m_pq->at(j);return m_keys->at(i) < m_keys->at(j);
}template<class Key>
bool IndexMinPQ<Key>::less(int x, int y)
{
    x = m_pq->at(x);y = m_pq->at(y);return m_keys->at(x) > m_keys->at(y);
}template<class Key>
void IndexMinPQ<Key>::validateIndex(int idx)
{
    if (idx<1 || idx>m_maxN) {
    out("index error!\n");}
}void test_IndexMinPQ()
{
    double a[4] = {
     3.17,10.5,4.67,9.09 };IndexMinPQ<double> minPQ(9);for (int i = 0; i < 4; ++i) {
    minPQ.insert(i + 1, a[i]);}out(minPQ.min()), hh;minPQ.change(3, 2.09);out(minPQ.min()), hh;minPQ.change(4, 1.89);out(minPQ.min()), hh;}int main() {
    test_IndexMinPQ();system("pause");return 0;
}