Priority Queue Vocabulary

A priority queue always removes the element with the highest priority first, regardless of the order elements were originally added in, and it's typically implemented internally with a heap, which keeps both insertion and removal of the highest-priority element efficient. A plain FIFO queue instead always removes whichever element was added first, with no notion of priority at all. This priority-based removal order is exactly why a priority queue, not a plain queue, is the standard structure behind things like a task scheduler or an event simulation that needs to process the most urgent item next.

The heap provides efficient insert and remove-highest-priority operations, since its shallow, balanced shape means both inserting a new element and removing the current highest-priority one only ever need to adjust a small number of elements along one path, keeping both operations logarithmic in the total number of elements stored. Scanning a plain unsorted list for the highest-priority element every single time would instead cost linear time on every single removal, which gets slower and slower as more elements accumulate. This logarithmic guarantee is exactly why a heap, rather than a plain list, is the standard backing structure for a priority queue.

This is a priority queue with a linear-time removal operation, since scanning the entire unsorted list to find the highest-priority element on every single removal costs time proportional to how many elements are currently stored, which is far slower than the logarithmic cost a heap-backed implementation would provide. A cache eviction policy is an unrelated concept about discarded cache entries. This linear-scan pattern is exactly the kind of implementation detail a performance-focused reviewer flags, since it technically satisfies the priority-queue interface while giving up the whole performance benefit a heap is meant to provide.

Backing the priority queue with a heap restores both insertion and highest-priority removal to logarithmic time regardless of how many tasks are currently pending, which is exactly the fix for the throughput degradation described in this incident. Continuing to back it with a plain unsorted list that's scanned in full on every removal is exactly what let throughput degrade sharply as the pending-task count grew. This heap-backed implementation is the standard, well-understood fix, and it's essentially always the right default unless the workload has some unusual property that makes a different structure genuinely better suited.

Keeping a list fully sorted at all times means every single insertion has to find the correct position and shift other elements to make room, which costs linear time per insert even though removal of the highest-priority element becomes instant. A heap instead keeps both insertion and highest-priority removal logarithmic, trading a slightly more expensive removal than an always-sorted list's instant one for a dramatically cheaper insertion, which wins out overall for a workload with frequent insertions mixed with removals. The tradeoff is exactly this balance between insert cost and removal cost, and a heap is the structure that keeps both operations reasonably fast rather than optimizing one at the total expense of the other.