Dart HeapPriorityQueue
last modified April 4, 2025
In Dart, HeapPriorityQueue is an implementation of a priority queue based on a heap data structure. It maintains elements in order according to their priority.
Elements are ordered either by their natural ordering or by a comparator function. The highest priority element is always at the front of the queue.
Creating a HeapPriorityQueue
The simplest way to create a HeapPriorityQueue is using the constructor with a comparator function.
import 'dart:collection';
void main() {
var pq = HeapPriorityQueue<int>((a, b) => a.compareTo(b));
pq.add(5);
pq.add(3);
pq.add(7);
pq.add(1);
print(pq.removeFirst()); // 1 (highest priority)
print(pq.removeFirst()); // 3
}
We create a min-heap priority queue that orders integers in ascending order. The comparator function defines the priority order. removeFirst always returns the highest priority element.
$ dart main.dart 1 3
Custom Comparator for Objects
We can use custom objects with a comparator function to define priority.
import 'dart:collection';
class Task {
final String name;
final int priority;
Task(this.name, this.priority);
@override
String toString() => '$name ($priority)';
}
void main() {
var taskQueue = HeapPriorityQueue<Task>(
(a, b) => b.priority.compareTo(a.priority) // Max-heap
);
taskQueue.add(Task('Write report', 2));
taskQueue.add(Task('Fix bug', 5));
taskQueue.add(Task('Test feature', 3));
while (taskQueue.isNotEmpty) {
print(taskQueue.removeFirst());
}
}
We create a max-heap priority queue for Task objects. Higher priority numbers come first. The comparator reverses the comparison to create a max-heap.
$ dart main.dart Fix bug (5) Test feature (3) Write report (2)
Basic Operations
HeapPriorityQueue provides essential queue operations like add, remove, and peek.
import 'dart:collection';
void main() {
var pq = HeapPriorityQueue<int>((a, b) => a.compareTo(b));
// Add elements
pq.add(10);
pq.addAll([5, 15, 3]);
// Check properties
print('Length: ${pq.length}');
print('First element: ${pq.first}');
print('Is empty: ${pq.isEmpty}');
// Remove elements
print('Removed: ${pq.removeFirst()}');
print('Removed: ${pq.removeFirst()}');
}
This demonstrates basic operations. addAll adds multiple elements. first peeks at the highest priority element without removing it. removeFirst removes and returns it.
$ dart main.dart Length: 4 First element: 3 Is empty: false Removed: 3 Removed: 5
Handling Duplicates
HeapPriorityQueue can handle duplicate elements while maintaining order.
import 'dart:collection';
void main() {
var pq = HeapPriorityQueue<int>((a, b) => a.compareTo(b));
pq.addAll([5, 3, 5, 7, 3, 1]);
print('All elements:');
while (pq.isNotEmpty) {
print(pq.removeFirst());
}
print('\nContains 5: ${pq.contains(5)}');
pq.add(5);
print('Contains 5 after add: ${pq.contains(5)}');
}
Duplicate values are allowed in the priority queue. The contains method checks for element presence. The queue maintains order even with duplicates.
$ dart main.dart All elements: 1 3 3 5 5 7 Contains 5: false Contains 5 after add: true
Priority Queue with Custom Ordering
We can implement complex ordering logic with custom comparators.
import 'dart:collection';
class Student {
final String name;
final double gpa;
final int credits;
Student(this.name, this.gpa, this.credits);
@override
String toString() => '$name (GPA: $gpa, Credits: $credits)';
}
void main() {
var studentQueue = HeapPriorityQueue<Student>((a, b) {
// Primary sort by GPA (descending), secondary by credits (ascending)
var gpaCompare = b.gpa.compareTo(a.gpa);
if (gpaCompare != 0) return gpaCompare;
return a.credits.compareTo(b.credits);
});
studentQueue.add(Student('Alice', 3.7, 90));
studentQueue.add(Student('Bob', 3.9, 85));
studentQueue.add(Student('Charlie', 3.7, 95));
studentQueue.add(Student('David', 3.5, 100));
print('Students in priority order:');
while (studentQueue.isNotEmpty) {
print(studentQueue.removeFirst());
}
}
We implement a multi-level comparator that first sorts by GPA (descending) then by credits (ascending). This shows the flexibility of HeapPriorityQueue ordering.
$ dart main.dart Students in priority order: Bob (GPA: 3.9, Credits: 85) Alice (GPA: 3.7, Credits: 90) Charlie (GPA: 3.7, Credits: 95) David (GPA: 3.5, Credits: 100)
Best Practices
- Comparator Choice: Carefully design comparators for correct ordering.
- Immutable Elements: Use immutable objects to prevent order corruption.
- Performance: Adding/removing is O(log n), peeking is O(1).
- Bulk Operations: Use addAll for better performance with multiple adds.
Source
Dart HeapPriorityQueue Documentation
This tutorial covered Dart's HeapPriorityQueue with practical examples demonstrating its key features and usage patterns for priority-based processing.
Author
List all Dart tutorials.