DSA in DartHard40 XP4 min read
How do you implement a priority queue in Dart?
TL;DR: Dart's package:collection provides HeapPriorityQueue<E> — a min-heap by default. O(log n) add, O(log n) removeFirst, O(1) first. Used for Dijkstra's shortest path, task scheduling, and top-K problems.
Full Answer
A priority queue always gives you the highest (or lowest) priority element first, regardless of insertion order. Internally implemented as a binary heap.
Heap Properties
- ▸Min-heap: parent is always smaller than children (fastest to get minimum)
- ▸Max-heap: parent is always larger (fastest to get maximum)
- ▸Add: insert at end, bubble up — O(log n)
- ▸RemoveFirst: swap root with last, bubble down — O(log n)
- ▸Peek: root element — O(1)
🎯
Top-K problem: find K largest elements in a stream. Use a min-heap of size K — discard elements smaller than the heap's minimum. Final heap contains top-K.
Code Examples
dartPriority queue for top-K and task scheduling
Output
Fix crash [5, 11, 12]
Common Mistakes
- ✗Using List.sort() for a priority queue — O(n log n) vs heap's O(log n) per operation
- ✗Forgetting that HeapPriorityQueue requires package:collection as a dependency
Interview Tip
💡
Top-K problems are extremely common in interviews. The trick: use a min-heap of size K and discard elements smaller than the minimum. This gives O(n log K) instead of O(n log n) sort.
#priority-queue#heap#data-structures#collection