优先队列

🍠优先队列的实现有三种：

• 有序数组
• 无序数组
• 堆

🍅有序数组

#include <vector>
#include <algorithm>
#include  <functional>
#include <iostream>
#include "Common.hpp"
using namespace std;

/**
 * 优先队列
 * 2.4.3 有序数组实现
 **/ 
template<typename T>
class OrderArrayMaxPQ {
  private:
    pair<int, T>* arr;
    int N;
    int _capacity;
  public:
    void show() const ;
    explicit OrderArrayMaxPQ(int max);
    ~OrderArrayMaxPQ() {delete [] arr;}
    // explicit OrderArrayMaxPQ(std::initializer_list<pair<int, T>>);
    void insert(pair<int, T>);
    pair<int, T> delMax();
    bool isEmpty() const { return N == 0;}
    int size() const {return N;} 
    int capacity() const {return _capacity;}
};

template<typename T>
OrderArrayMaxPQ<T>::OrderArrayMaxPQ(int max) :
  arr(new pair<int, T>[max]()), N(0), _capacity(max)
{
}

// template<typename T>
// OrderArrayMaxPQ<T>::OrderArrayMaxPQ(std::initializer_list<pair<int, T>> l) 
//   : arr(new pair<int, T>[l.size()]()), N(l.size()), _capacity(l.size())
// {
//   copy(l.begin(), l.end(), arr);
// }

template<typename T>
void OrderArrayMaxPQ<T>::insert(pair<int, T> x) {
  if(capacity() == size()) 
    return ;
  arr[N++] = x;
  for(int i = N - 1; i > 0 && arr[i] < arr[i - 1]; --i)
    swap(arr[i], arr[i - 1]); 
}

template<typename T>
pair<int, T> OrderArrayMaxPQ<T>::delMax() {
  pair<int ,T> res;
  if(isEmpty())
    return res;
  res = arr[N - 1];
  arr[--N] = pair<int , T>();
  return res;
}

template<typename T>
void OrderArrayMaxPQ<T>::show() const {
  cout << "N: " << size() << " arr: ";
  for(int i = 0; i < N; ++i)
    cout << arr[i].first << " ";
  cout << endl;
}

int main(int argc, char** argv) {
  OrderArrayMaxPQ<int> pq(20);
  vector<int> v = Common::getInstance()->getRandomVector(12);
  for(auto x: v) {
    pq.insert({x, x});
  }
  while(pq.size()) {
    pq.show();
    pq.delMax();
  }
}

🥦无序数组

#include <vector>
#include <algorithm>
#include  <functional>
#include <iostream>
#include "Common.hpp"
using namespace std;

/**
 * 优先队列
 * 2.4.3 无序数组实现
 **/ 
template<typename T>
class UnOrderArrayMaxPQ {
  private:
    pair<int, T>* arr;
    int N;
    int _capacity;
  public:
    void show() const ;
    explicit UnOrderArrayMaxPQ(int max);
    ~UnOrderArrayMaxPQ() {delete [] arr;}
    explicit UnOrderArrayMaxPQ(std::initializer_list<pair<int, T>>);
    void insert(pair<int, T>);
    pair<int, T> delMax();
    bool isEmpty() const { return N == 0;}
    int size() const {return N;} 
    int capacity() const {return _capacity;}
};

template<typename T>
UnOrderArrayMaxPQ<T>::UnOrderArrayMaxPQ(int max) :
  arr(new pair<int, T>[max]()), N(0), _capacity(max)
{
}

template<typename T>
UnOrderArrayMaxPQ<T>::UnOrderArrayMaxPQ(std::initializer_list<pair<int, T>> l) 
  : arr(new pair<int, T>[l.size()]()), N(l.size()), _capacity(l.size())
{
  copy(l.begin(), l.end(), arr);
}

template<typename T>
void UnOrderArrayMaxPQ<T>::insert(pair<int, T> x) {
  if(capacity() == size()) 
    return ;
  arr[N++] = x;
}

template<typename T>
pair<int, T> UnOrderArrayMaxPQ<T>::delMax() {
  if(isEmpty())
    return pair<int, T>();
  int max_one = 0;
  for(int i = 0; i < N; ++i) 
    if(arr[max_one].first < arr[i].first) {
      max_one = i;
    }
  swap(arr[max_one], arr[--N]);
  pair<int,T> res = arr[N];
  arr[N] = pair<int,T>();
  return res;
}

template<typename T>
void UnOrderArrayMaxPQ<T>::show() const {
  cout << "N: " << size() << " arr: ";
  for(int i = 0; i < N; ++i)
    cout << arr[i].first << " ";
  cout << endl;
}

int main(int argc, char** argv) {
  UnOrderArrayMaxPQ<int> pq(20);
  vector<int> v = Common::getInstance()->getRandomVector(12);
  for(auto x: v) {
    pq.insert({x, x});
  }
  while(pq.size()) {
    pq.show();
    pq.delMax();
  }
}

🥧堆

#include <vector>
#include <algorithm>
#include  <functional>
#include <iostream>
#include "Common.hpp"
#include <limits>
using namespace std;

/**
 * 优先队列
 * 二叉堆实现
 **/ 
template<typename T>
class MaxPQ {
  private:
    pair<int, T>* arr;
    int N;
    int _capacity;
    void swim(int i);
    void sink(int i);
  public:
    void show() const ;
    explicit MaxPQ(int max);
    ~MaxPQ() {delete [] arr;}
    void insert(pair<int, T>);
    pair<int, T> delMax();
    bool isEmpty() const { return N == 0;}
    int size() const {return N;} 
    int capacity() const {return _capacity;}
};

template<typename T>
MaxPQ<T>::MaxPQ(int max) :
  arr(new pair<int, T>[max + 1]()), N(0), _capacity(max + 1)
{
  arr[0] = pair<int, T>(INT8_MIN, T());
}

template<typename T>
void MaxPQ<T>::insert(pair<int, T> x) {
  if(capacity() == size()) 
    return ;
  arr[++N] = x;
  swim(N);
}

template<typename T>
pair<int, T> MaxPQ<T>::delMax() {
  pair<int ,T> res;
  if(isEmpty())
    return res;
  swap(arr[N--], arr[1]);
  res =  arr[N + 1];
  arr[N + 1] = pair<int ,T>();
  sink(1);
  return res;
}

template<typename T>
void MaxPQ<T>::show() const {
  cout << "N: " << size() << " arr: ";
  for(int i = 1; i <= N; ++i)
    cout << arr[i].first << " ";
  cout << endl;
}

template<typename T>
void MaxPQ<T>::swim(int i) {
  while(i > 1) {
    if(arr[i].first > arr[i / 2].first) swap(arr[i], arr[i / 2]);
    i /= 2;
  }
}

template<typename T>
void MaxPQ<T>::sink(int i) {
  int k;
  while(i < N) {
    k = 2 * i;
    if(arr[k].first < arr[k + 1].first) ++k;
    if(arr[k].first <= arr[i].first) break;
    swap(arr[k], arr[i]);
    i = k;
  }
}

int main(int argc, char** argv) {
  MaxPQ<int> pq(20);
  vector<int> v = Common::getInstance()->getRandomVector(12);
  for(auto x: v) {
    pq.insert({x, x});
    // pq.show();
  }
  while(pq.size()) {
    pq.show();
    pq.delMax();
  }
}

🥨时间复杂度对比

• 有序数组： 插入：N，删除：1
• 无序数组： 插入：1，删除：N
• 堆：插入、删除：lgN
• 理想情况：都是1