Is a heap the same thing?

A heap is one implementation; a priority queue is the abstract behavior.

Can priorities change?

Yes, if the implementation updates its ordering correctly or replaces outdated records safely.

Does priority mean probability?

No. A priority can represent cost, time, urgency, or another ordered quantity.

AI Glossary / Graphs and symbolic AI / Advanced

Priority queue

Definition

A priority queue is a data structure that returns the item with the best priority according to a specified ordering. Unlike an ordinary first-in, first-out queue, it can select an item added later. In AI search, the priority often comes from a cost or evaluation function.

What it means

A queue answers the question, “Which item should be handled next?” A priority queue answers using a ranking rule rather than arrival time alone. The rule might favor the lowest estimated route cost, the earliest simulated event, or the largest expected benefit from another computation.
The meaning of “best” must be explicit. A smaller number can mean greater urgency in one application, while a larger number means greater urgency in another. The queue enforces the chosen ordering; it does not decide whether the rule is useful, fair, or appropriate for the problem.

How it works

Typical operations insert an item with its priority, inspect the best item, and remove that item. A binary heap is a common implementation. In a min-heap, every parent has a key no greater than its children, putting a smallest key at the root. This does not fully sort the stored array.
For n items, a conventional binary heap supports inspecting the root in constant time and insertion or root removal with logarithmic heap-adjustment work. These bounds assume constant-time comparisons and abstract away occasional storage resizing. Other implementations have different tradeoffs.
Equal priorities need a tie rule if predictable order matters. An arrival counter can preserve insertion order among ties. Changing a pending item's priority requires a supported update operation or a replacement strategy; simply editing a stored key may break the ordering. One replacement approach marks an old record obsolete, inserts a new record, and skips obsolete records when removing items.

Three practical examples

A route-search program keeps candidate paths ordered by estimated total cost. It expands the best-ranked candidate next, while the surrounding search algorithm handles repeated states and termination conditions.
A factory simulator keeps future events ordered by simulated time. A machine completion at time 12 is processed before an arrival at time 15, regardless of which event was inserted first.
A planning agent ranks pending value updates by estimated impact. Newly discovered information can make an update more urgent than work that has waited longer.

Think of it this way

Imagine a dispatch board that continually puts the most urgent job at the top. New work can jump ahead, and a revised urgency can change a pending job's position. The board organizes selection; separate rules determine urgency and whether an already-started job can be interrupted.

Worked example

Suppose four fictional jobs arrive in the order A, B, C, D. Their priority numbers are 7, 2, 5, and 2. Smaller means more urgent, and equal numbers are resolved by original arrival order.
Initially, repeated removal would produce B, D, C, A. B wins its tie with D because B arrived earlier. A arrived first but has the least urgent number.
Now remove only B. Before the next removal, C's priority improves from 5 to 1. The remaining order becomes C, D, A. Across the whole sequence, the jobs are therefore handled as B, C, D, A.
If the implementation uses replacement records, C may temporarily have both an old priority-5 record and a new priority-1 record stored internally. The old record must be identified as obsolete. It must not cause C to run twice when later encountered.
Separately, the numeric array [1, 4, 2, 7, 6, 3] satisfies the min-heap parent-child rule: 1 precedes children 4 and 2, 4 precedes 7 and 6, and 2 precedes 3. Yet the array is not sorted because 4 appears before 2. The guarantee concerns the next extraction, not ordinary array iteration.

Illustrative case study

A fictional support team gives incidents urgency scores from 1 to 5, with 1 highest. Its first implementation correctly picks urgent tickets but resolves equal scores using ticket identifiers. Staff had expected arrival order, so some older tickets appear to be overlooked.
The team adds an explicit arrival-based tie rule and tests it with small, recorded sequences. It also defines what happens when a ticket is reclassified: retaining its original arrival time or treating the change as a fresh entry can produce different outcomes among equal scores.
Later, the team notices that a continuous stream of score-1 tickets can delay score-5 tickets indefinitely. It evaluates an aging policy that changes priorities as tickets wait. That policy is a separate design decision and requires correct priority updates. The case illustrates requirements and testing, not a measured service improvement.

Common misconceptions and mistakes

A priority queue is not automatically a fully sorted list. Reading its internal storage in order may produce an unexpected sequence.
Equal-priority items do not necessarily retain arrival order unless the implementation promises or explicitly implements that behavior.
Choosing the smallest score is not always correct; it depends on the score's meaning. A max-priority application requires the opposite ordering.
A correct queue does not make every search optimal or every schedule fair. Those properties depend on the surrounding algorithm, scoring rule, constraints, and workload.

Business use

Priority queues help allocate attention in search, simulation, job scheduling, and operational software. Define priority direction, tie handling, update rules, and cancellation behavior before choosing an implementation. Measure waiting times across job categories as well as throughput. If jobs can be interrupted, specify that separately: selecting the next job does not by itself provide preemption or manage concurrent workers.

Check your understanding

Why does B precede D initially?

Answer: They share priority 2, and B arrived earlier under the stated tie rule.

What happens after C changes to priority 1?

Answer: C becomes the next job, ahead of D and A.

Can the example heap array be read as a sorted list?

Answer: No; only its parent-child ordering is guaranteed.

Related terms

Learn next

Trace insertions and removals in a small binary heap. Then examine how a search algorithm chooses priorities and handles stale records, ties, and repeated states.

Search algorithm

Sources

Cornell University, Priority Queues and Binary Heaps lecture: https://www.cs.cornell.edu/courses/cs312/2007sp/lectures/lec25.html Python documentation, heapq and priority queue implementation notes: https://docs.python.org/3/library/heapq.html AIMA glossary, priority queue entry: https://github.com/aimacode/aima-glossary

Previous: Prioritized sweeping Next: Privacy