Dart PriorityQueue
last modified April 4, 2025
In Dart, PriorityQueue is a collection that maintains elements in priority order. It provides efficient insertion and removal of the highest priority element.
PriorityQueue implements a heap data structure internally. Elements are ordered based on their natural ordering or a custom comparator function.
Creating a PriorityQueue
The simplest way to create a PriorityQueue is using the constructor.
import 'dart:collection';
void main() {
var queue = PriorityQueue<int>();
queue.addAll([5, 3, 7, 1, 9]);
print(queue);
print('Removed: ${queue.removeFirst()}');
print(queue);
}
We create a PriorityQueue of integers. The addAll method adds multiple elements. The removeFirst method removes and returns the highest priority element.
$ dart main.dart
{1, 3, 5, 7, 9}
Removed: 1
{3, 5, 7, 9}
Custom Comparator
We can define custom ordering using a comparator function.
import 'dart:collection';
void main() {
var queue = PriorityQueue<String>((a, b) => b.length.compareTo(a.length));
queue.addAll(['apple', 'banana', 'kiwi', 'orange']);
print(queue);
print('Longest: ${queue.first}');
}
This PriorityQueue orders strings by length in descending order. The comparator function compares string lengths rather than lexicographical order.
$ dart main.dart
{banana, orange, apple, kiwi}
Longest: banana
PriorityQueue with Objects
We can use custom objects with PriorityQueue by implementing Comparable.
import 'dart:collection';
class Task implements Comparable<Task> {
final String name;
final int priority;
Task(this.name, this.priority);
@override
int compareTo(Task other) => priority.compareTo(other.priority);
@override
String toString() => '$name ($priority)';
}
void main() {
var queue = PriorityQueue<Task>();
queue.addAll([
Task('Write report', 3),
Task('Fix bug', 1),
Task('Test feature', 2)
]);
while (queue.isNotEmpty) {
print('Processing: ${queue.removeFirst()}');
}
}
The Task class implements Comparable to define priority ordering. The queue processes tasks from highest to lowest priority number.
$ dart main.dart Processing: Write report (3) Processing: Test feature (2) Processing: Fix bug (1)
PriorityQueue Operations
PriorityQueue provides various operations for queue management.
import 'dart:collection';
void main() {
var queue = PriorityQueue<int>();
// Add elements
queue.add(5);
queue.add(3);
queue.add(7);
// Check properties
print('Length: ${queue.length}');
print('First: ${queue.first}');
print('Last: ${queue.last}');
print('Contains 3: ${queue.contains(3)}');
// Remove elements
queue.remove(3);
print('After remove: $queue');
// Clear queue
queue.clear();
print('After clear: $queue');
}
This demonstrates common PriorityQueue operations. Note that last requires traversing the heap and is O(n) complexity.
$ dart main.dart
Length: 3
First: 3
Last: 7
Contains 3: true
After remove: {5, 7}
After clear: {}
PriorityQueue with Duplicates
PriorityQueue can handle duplicate elements while maintaining order.
import 'dart:collection';
void main() {
var queue = PriorityQueue<int>();
queue.addAll([5, 3, 5, 7, 3, 1]);
print('Original: $queue');
// Remove all elements in order
print('Processing order:');
while (queue.isNotEmpty) {
print(queue.removeFirst());
}
}
Duplicate values are maintained in the queue. The removeFirst method always returns the smallest remaining element when duplicates exist.
$ dart main.dart
Original: {1, 3, 3, 5, 5, 7}
Processing order:
1
3
3
5
5
7
Best Practices
- Comparator Consistency: Ensure comparator provides total ordering.
- Immutable Elements: Avoid modifying elements after insertion.
- Performance: add/removeFirst are O(log n), contains is O(n).
- Null Safety: Consider non-nullable types for clarity.
Source
Dart PriorityQueue Documentation
This tutorial covered Dart's PriorityQueue with practical examples demonstrating its key features and usage patterns.
Author
List all Dart tutorials.