lurenaa的博客

🥛分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class IndexMaxPQ...{
    private int maxN;        // maximum number of elements on PQ
    private int n;           // number of elements on PQ
    private int[] pq;        // binary heap using 1-based indexing
    private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
    private Key[] keys;      // keys[i] = priority of i

//中间省略...
public void insert(int i, Key key) {
        ...
        n++;
        qp[i] = n;
        pq[n] = i;
        keys[i] = key;
        swim(n);
}

  根据《算法4》给出的代码，分析这两段代码我们可以看出来：

  • 在定义处可知pq是二叉堆的数组
  • 由qp[i] = n;
    pq[n] = i;可以看出来，qp这个数组的用处就是为了记录**pq中值为i的下标是多少**，这样当我们要改下标为i的元素的值时，我们就不用遍历pq来获得位置了，**用空间来换取时间**
  • 并且这个索引i仅仅为了找到元素对象key，并没实际的意义。n才是对应二叉堆的位置。

😍代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <vector>
#include <algorithm>
#include  <functional>
#include <iostream>
#include "Common.hpp"
#include <limits>
using namespace std;

/**
 * 索引最小优先队列
 **/ 
template<typename T>
class IndexMinPQ {
  public:
    IndexMinPQ(int max);
    void show() const;
    int size() const {return N;}
    int capacity() const {return _capacity;}
    void insert(int k, T item);
    void change(int k, T item);
    bool contain(int k) const {return qp[k] != -1;};
    int delMin();
  private:
    void sink(int i);
    void swim(int i);
    T* element; //元素
    int* pq; //二叉堆
    int *qp; //index
    int N;
    int _capacity;
};

template<typename T>
IndexMinPQ<T>::IndexMinPQ(int max) :
  element(new T[max + 1]), pq(new int[max + 1])
  , qp(new int[max + 1]), N(0), _capacity(max) 
{
  for(int i = 0; i < max + 1; ++i)
    qp[i] = -1;
}

template<typename T>
void IndexMinPQ<T>::sink(int n){
  while(n < N) {
    int m = n * 2;
    if(element[pq[m]] > element[pq[m + 1]]) ++m;
    if(element[pq[m]] < element[pq[n]]) break;
    swap(pq[m], pq[n]);
    swap(qp[pq[m]], qp[pq[n]]);
    n = m;
  }
}

template<typename T>
void IndexMinPQ<T>::swim(int n) {
  while(n > 1) {
    int m = n / 2;
    if(element[pq[m]] <= element[pq[n]]) break;
    swap(pq[m], pq[n]);
    swap(qp[pq[m]], qp[pq[n]]);
    n = m; 
  }
}


template<typename T>
void IndexMinPQ<T>::insert(int k, T item) {
  // cout << "insert " << k << " " << item << endl;
  if(capacity() == size()){
    cout << "out of size" << endl;
    return ;
  }
  pq[++N] = k;
  element[k] = item;
  qp[k] = N;
  swim(N);
  // show();
}

template<typename T>
void IndexMinPQ<T>::show() const
{
  cout << "pq: ";
  for(int i = 1; i <= capacity(); ++i) 
    cout << pq[i] << " ";
  cout << endl;
  cout << "qp: ";
  for(int i = 1; i <= capacity(); ++i) 
    cout << qp[i] << " ";
  cout << endl;
  cout << "element: ";
  for(int i = 1; i <= capacity(); ++i) 
    cout << element[i] << " ";
  cout << endl;
}

template<typename T>
void IndexMinPQ<T>::change(int k, T item) {
  if(!contain(k)) {
    cout << "change not contain" << endl;
    return ;   
  }
  T old_one = element[k];
  element[k] = item;
  if(item > old_one) 
    sink(qp[k]);
  else if(item < old_one)
    swim(qp[k]);
}

template<typename T>
int IndexMinPQ<T>::delMin() {
  int max = pq[1];
  swap(pq[1], pq[N]);
  swap(qp[pq[1]], qp[pq[N]]);
  --N;
  show();
  sink(1);
  show();
  qp[max] = -1;
  element[max] = -1;
  pq[N + 1] = -1;
  return max;
}

int main(int argc, char** argv) {
  IndexMinPQ<int> pq(6);
  vector<int> v = Common::getInstance()->getRandomVector(6);
  for(size_t i = 0; i < v.size(); ++i) {
    pq.insert(i + 1, v[i]);
  }
  pq.show();
  pq.delMin();
  pq.show();
  return 0;
}

🍠参考资料：链接


 上一页

算法