-
Notifications
You must be signed in to change notification settings - Fork 0
/
minPQ.h
107 lines (90 loc) · 1.89 KB
/
minPQ.h
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
#ifndef MINPQ_H
#define MINPQ_H
using namespace std;
#include "random.h"
//Priority Queue template that orders elements based on user-defined compare function
template <class T>
class minPQ{
public:
minPQ(){N = 0; pq[0] = nullptr;}
//Inserts element and restores heap
void insert(T v);
//Removes smallest element
void deleteMin();
//Checks if PQ is empty
bool isEmpty();
//Returns smallest element
T getMin();
//Returns number of elements in pq. NOT the array size.
int size();
//heap operations
void swap(int i, int j);
void swim(int k);
void sink(int k);
virtual bool compare(T* x, T* y) { return 0; }
int N; //current number of elements
T* pq[20]; //heap
};
template <class T>
void minPQ<T>::swap(int i, int j){
T* temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
template <class T>
void minPQ<T>::swim(int k){
compare(pq[k/2], pq[k]);
while (k > 1 && compare(pq[k/2], pq[k])){
swap(k/2, k);
k = k/2;
}
}
template <class T>
void minPQ<T>::sink(int k){
while (2*k <= N){
int j = 2*k;
if (j < N && compare(pq[j], pq[j+1])){
j++;
}
if (!compare(pq[k], pq[j])){
break;
}
swap(k, j);
k = j;
}
}
template <class T>
void minPQ<T>::insert(T v){
pq[++N] = &v;
swim(N);
}
template <class T>
void minPQ<T>::deleteMin(){
if(!isEmpty()){
swap(1, N);
pq[N] = NULL;
N--;
sink(1);
}
else if (isEmpty()){
cout << "Error. Priority Queue is empty." << endl;
exit(1);
}
}
template <class T>
bool minPQ<T>::isEmpty(){
if (N == 0){
return true;
}else{
return false;
}
}
template <class T>
T minPQ<T>::getMin(){
return *pq[1];
}
template <class T>
int minPQ<T>::size(){
return N;
}
#endif //minPQ