Priority Queue (ADT)
An abstract data type where each element has a 'priority' and the highest priority is served first.
Heap Operations
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
In a standard Queue, it's 'First Come, First Served'. In a Priority Queue, it's 'VIPs First'.
Imagine an Emergency Room. A patient with a heart attack (High Priority) is treated before someone with a cold (Low Priority), regardless of who arrived first.
Concept
A Priority Queue is an Abstract Data Type (ADT). It is defined by its behavior, not its implementation.
- Insert(item, priority): Add an item with an assigned priority.
- Peek(): View the highest priority item.
- Pop(): Remove and return the highest priority item.
How it Works
While you can implement a PQ using an unsorted array (O(1) insert, O(N) pop) or a sorted array (O(N) insert, O(1) pop), the most efficient standard implementation is a Binary Heap.
A Binary Heap allows both Insert and Pop in O(log N) time, offering the best balance.
Step-by-Step Breakdown
- Insertion: Add element to the end of the heap, then 'bubble up' to restore heap property.
- Extraction: Remove root (max priority), move last element to root, then 'bubble down'.
When to Use
- Dijkstra's Algorithm / A*: Fetching the next closest node.
- Huffman Coding: Building efficient compression trees.
- Scheduling: Operating system process scheduling by priority.
- Top K Elements: Keeping track of the largest K items in a stream.
When NOT to Use
- When simple FIFO behavior is required (use Queue).
- When you need to search for arbitrary elements (use a BST or Hash Map).
How to Identify
Keywords like 'k-th largest', 'k-th smallest', 'closest points', or 'task scheduler' are strong indicators for a Priority Queue (Heap).
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.