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
|
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifndef ds_PriorityQueue_h
#define ds_PriorityQueue_h
#include "js/Vector.h"
namespace js {
/*
* Class which represents a heap based priority queue using a vector.
* Inserting elements and removing the highest priority one are both O(log n).
*
* Template parameters are the same as for Vector, with the addition that P
* must have a static priority(const T&) method which returns higher numbers
* for higher priority elements.
*/
template <class T, class P, size_t MinInlineCapacity = 0,
class AllocPolicy = TempAllocPolicy>
class PriorityQueue {
Vector<T, MinInlineCapacity, AllocPolicy> heap;
PriorityQueue(const PriorityQueue&) = delete;
PriorityQueue& operator=(const PriorityQueue&) = delete;
public:
explicit PriorityQueue(AllocPolicy ap = AllocPolicy())
: heap(std::move(ap)) {}
[[nodiscard]] bool reserve(size_t capacity) { return heap.reserve(capacity); }
size_t length() const { return heap.length(); }
bool empty() const { return heap.empty(); }
T removeHighest() {
T highest = heap[0];
T last = heap.popCopy();
if (!heap.empty()) {
heap[0] = last;
siftDown(0);
}
return highest;
}
[[nodiscard]] bool insert(const T& v) {
if (!heap.append(v)) {
return false;
}
siftUp(heap.length() - 1);
return true;
}
void infallibleInsert(const T& v) {
heap.infallibleAppend(v);
siftUp(heap.length() - 1);
}
private:
/*
* Elements of the vector encode a binary tree:
*
* 0
* 1 2
* 3 4 5 6
*
* The children of element N are (2N + 1) and (2N + 2).
* The parent of element N is (N - 1) / 2.
*
* Each element has higher priority than its children.
*/
void siftDown(size_t n) {
while (true) {
size_t left = n * 2 + 1;
size_t right = n * 2 + 2;
if (left < heap.length()) {
if (right < heap.length()) {
if (P::priority(heap[n]) < P::priority(heap[right]) &&
P::priority(heap[left]) < P::priority(heap[right])) {
swap(n, right);
n = right;
continue;
}
}
if (P::priority(heap[n]) < P::priority(heap[left])) {
swap(n, left);
n = left;
continue;
}
}
break;
}
}
void siftUp(size_t n) {
while (n > 0) {
size_t parent = (n - 1) / 2;
if (P::priority(heap[parent]) > P::priority(heap[n])) {
break;
}
swap(n, parent);
n = parent;
}
}
void swap(size_t a, size_t b) {
T tmp = heap[a];
heap[a] = heap[b];
heap[b] = tmp;
}
};
} /* namespace js */
#endif /* ds_PriorityQueue_h */
|
