A Priority Queue is a special type of queue where each element is associated with a priority. Elements with higher priority are served before elements with lower priority. If two elements have the same priority, they are served according to their order in the queue.

Think of an Emergency Room (ER) at a hospital:

1. People arrive at different times (arrivalTime).
2. However, the order of treatment isn't "First-Come, First-Served".
3. A person with a minor scratch (Low Priority) might arrive first, but a person with a broken leg (High Priority) will be seen before them, even if they arrive later.

---

Implementation: The Heap

While you could use a sorted array ($O(n)$ insertion), Priority Queues are almost always implemented using a Binary Heap.

• Min-Heap: The smallest element is always at the root.
• Max-Heap: The largest element is always at the root.

Complexity

---

JavaScript doesn't have a built-in Priority Queue (unlike Java's PriorityQueue or C++'s priority_queue). In interviews, you usually describe the Heap logic or use a simple sorted-array approach if $N$ is small.

javascript Standard
/**
 * Simple Priority Queue (using Sorted Array for simplicity)
 * Note: Real implementation should use a Binary Heap.
 */
class PriorityQueue {
  constructor() {
    this.values = [];
  }

  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }

  dequeue() {
    return this.values.shift();
  }

  sort() {
    // Standard sort: Lowest priority number = Highest importance
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

/**
 * Top K Frequent Elements Pattern
 */
function topKFrequent(nums, k) {
  const count = new Map();
  for (let n of nums) count.set(n, (count.get(n) || 0) + 1);

  // Using an array as a pseudo-PriorityQueue
  const pq = Array.from(count.entries());
  pq.sort((a, b) => b[1] - a[1]); // Descending by frequency
  
  return pq.slice(0, k).map(x => x[0]);
}

---

Use Cases

• Dijkstra’s Algorithm: Finding the shortest path in a weighted graph.
• Huffman Coding: Data compression.
• Merge K Sorted Lists: A classic hard task.
• CPU Scheduling: Prioritizing system processes.

Must-Practice Problems

• Kth Largest Element in an Array: Use a Min-Heap of size K.
• Find Median from Data Stream: (A high-tier question using two heaps).
• Task Scheduler: Efficiently arranging tasks with cooling periods.
• Minimum Cost to Connect Ropes: Always picking the two smallest.