Stage 1 · Code
Heaps & Priority Queues
Priority Queue
Priority queue using heap, custom comparators in Go.
6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Priority Queue Concept
A priority queue is an abstract data type where each element has a priority. Elements served by priority (not FIFO). Heap is the standard implementation: O(log n) insert/extract, O(1) peek.
Custom Comparators
Gopriority-queue-with-custom-ordering.go
35 linesLn 1, Col 1Go
Implement heap.Interface with custom Less. Index field enables O(log n) update via heap.Fix. Pop/Push maintain interface.
Common Use Cases
| Problem | PQ Strategy | Complexity |
|---|---|---|
| Dijkstra shortest path | Min-heap by distance | O((V+E) log V) |
| Top K elements | Min-heap size K | O(n log K) |
| Merge K sorted lists | Min-heap of list heads | O(N log K) |
| Task scheduler | Max-heap by priority | O(log n) per task |
| A* search | Min-heap by f = g + h | O(b^d) |
| Huffman coding | Min-heap by frequency | O(n log n) |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.