-
Notifications
You must be signed in to change notification settings - Fork 8
/
heap_based_priority_queue.dart
128 lines (105 loc) · 3.58 KB
/
heap_based_priority_queue.dart
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
import 'package:test/test.dart';
import '../../../../utils/list_extension.dart';
/// Note: While priority queues are often implemented using heaps, they are conceptually
/// distinct from heaps. A priority queue is an abstract data structure like a list
/// or a map; just as a list can be implemented with a linked list or with an array,
/// a priority queue can be implemented with a heap or another method such as an unordered array.
///
/// Pseudocode:
/// - Write a Min Binary Heap - lower number means higher priority.
/// - Each Node has a val value a priority. Use the priority to build the heap.
/// - Enqueue method accepts a value and priority, makes a new node,
/// and puts it in the right spot based off of its priority.
/// - Dequeue method removes root element, returns it, and rearranges heap using priority.
class Node<T> {
Node(this.value, this.priority);
T value;
num priority;
}
class PriorityQueue<T> {
final List<Node<T>> _heap = [];
void enqueue(T value, num priority) {
final newNode = Node(value, priority);
_heap.add(newNode);
_siftUp();
}
_siftUp() {
int childIndex = _heap.length - 1;
while (childIndex > 0) {
final parentIndex = (childIndex - 1) ~/ 2;
if (_heap[childIndex].priority >= _heap[parentIndex].priority) break;
_heap.swap(childIndex, parentIndex);
childIndex = parentIndex;
}
}
T? dequeue() {
if (_heap.isEmpty) return null;
_heap.swap(0, _heap.length - 1);
final oldRoot = _heap.removeLast();
_siftDown();
return oldRoot.value;
}
_siftDown() {
int parentIndex = 0;
while (true) {
final leftChildIndex = parentIndex * 2 + 1;
final rightChildIndex = leftChildIndex + 1;
if (leftChildIndex >= _heap.length) break;
final minChildIndex = rightChildIndex < _heap.length &&
_heap[rightChildIndex].priority < _heap[leftChildIndex].priority
? rightChildIndex
: leftChildIndex;
if (_heap[minChildIndex].priority >= _heap[parentIndex].priority) break;
_heap.swap(parentIndex, minChildIndex);
parentIndex = minChildIndex;
}
}
}
void main() {
group('enqueue', () {
test('should enqueue items and sift-up based on the priority', () {
final queue = PriorityQueue<String>();
// 1
// 2 5
// 6 3
queue.enqueue('some5', 5);
queue.enqueue('some6', 6);
queue.enqueue('some3', 3);
queue.enqueue('some1', 1);
queue.enqueue('some2', 2);
expect(queue._heap.map((e) => e.priority).toList(), [1, 2, 5, 6, 3]);
});
});
group('dequeue', () {
test(
'should dequeue root item after swapping with last item, then sift-down',
() {
final queue = PriorityQueue<String>();
// 1
// 2 5
// 6 3
queue.enqueue('some5', 5);
queue.enqueue('some6', 6);
queue.enqueue('some3', 3);
queue.enqueue('some1', 1);
queue.enqueue('some2', 2);
// 2
// 3 5
// 6
expect(queue.dequeue(), 'some1');
expect(queue._heap.map((e) => e.priority).toList(), [2, 3, 5, 6]);
// 3
// 6 5
expect(queue.dequeue(), 'some2');
expect(queue._heap.map((e) => e.priority).toList(), [3, 6, 5]);
expect(queue.dequeue(), 'some3');
expect(queue.dequeue(), 'some5');
expect(queue.dequeue(), 'some6');
expect(queue.dequeue(), isNull);
});
test('should return null if the queue is empty', () {
final queue = PriorityQueue();
expect(queue.dequeue(), isNull);
});
});
}