Heaps And Priority Queues

A heap keeps the highest- or lowest-priority item accessible without fully sorting every item after each insertion.

Why This Matters

Priority queues support schedulers, top-K results, retry timing, and best-first search when work arrives incrementally.

Working Model

Insertion and removal are logarithmic while peeking at the next item is constant time. PHP's SplPriorityQueue is a max-priority queue and extraction flags control whether data, priority, or both are returned.

Practical Rules

• Define whether higher or lower numbers run first.
• Add a deterministic sequence tie-breaker.
• Clone a priority queue before destructive iteration when needed.
• Separate priority from eligibility time.
• Use a bounded heap for top-K streams.

Failure Modes

• Assuming equal-priority order is stable.
• Using one priority number to encode unrelated policies.
• Iterating and accidentally consuming the queue.
• Re-sorting an entire growing list for every insertion.

Verification

• Test ties and negative priorities.
• Test extraction flags.
• Compare top-K output with a full sort.
• Measure incremental workloads.

What You Should Be Able To Do

After this lesson, you should be able to explain heap-backed priority queues and when partial ordering is preferable to full sorting, choose a suitable approach for a real PHP project, and verify the result instead of relying on assumptions.

Partial Order Instead Of Full Sort

A heap is useful when the program repeatedly needs the next highest-priority item but does not need every item fully sorted. A complete sort answers what is the entire ordered list? A priority queue answers what should come out next? That smaller promise can be much cheaper when work arrives incrementally or when the program only needs the top few items.

Schedulers, retry systems, best-first searches, leaderboards, and top-K reports all have this shape. New items arrive over time. The next item depends on priority. The program may insert more items after each removal. Sorting the whole list after every insertion is wasteful because most of the order is irrelevant. A heap maintains enough structure to find and remove the next item efficiently.

In PHP, SplPriorityQueue is the standard built-in priority queue. It is a max-priority queue, so higher priorities are extracted first. If the business meaning is lower number runs sooner, such as a timestamp or distance, the code must adapt the priority rule deliberately. Negating a number may be fine for a local algorithm, but operational code should make the direction clear in names and tests.

Basic Priority Queue Use

A priority queue stores data with a priority. Extraction removes the item with the highest priority according to the queue's comparison rules.

<?php

declare(strict_types=1);

$queue = new SplPriorityQueue();
$queue->insert('send receipt', 10);
$queue->insert('rebuild report', 1);
$queue->insert('charge card', 100);

echo $queue->extract() . PHP_EOL;
echo $queue->extract() . PHP_EOL;

// Prints:
// charge card
// send receipt

This example is intentionally simple. Production code should not hide unrelated policies inside one number. Urgency, eligibility time, tenant fairness, retry count, and manual override are different concepts. Combining them into a single priority value without a documented formula makes the system hard to reason about and harder to debug.

Ties And Determinism

Equal priorities need a policy. A priority queue is not automatically stable in the way a business user might expect. If two jobs have the same priority, the extraction order may not be the original insertion order unless the code encodes that behavior. For repeatable tests, pagination, or user-visible scheduling, add a deterministic tie-breaker.

One common approach is to store a composite priority, such as [priority, -sequence], when the queue comparison supports it. Another approach is to wrap data in a small object and compare using a custom structure outside SplPriorityQueue if the built-in behavior is not expressive enough. The important point is that ties are not an afterthought. They are part of the ordering contract.

<?php

declare(strict_types=1);

$queue = new SplPriorityQueue();
$sequence = 0;

$queue->insert('first high job', [10, -$sequence++]);
$queue->insert('second high job', [10, -$sequence++]);

while (!$queue->isEmpty()) {
    echo $queue->extract() . PHP_EOL;
}

// Prints:
// first high job
// second high job

The sequence value makes equal-priority order explicit. If the desired policy is newest first, use the sequence in the opposite direction and name that choice.

Extraction Flags And Destructive Iteration

SplPriorityQueue can return data, priorities, or both depending on its extraction flags. That is useful, but it is also a common source of confusion. Code that expects a job payload can break if another part of the program changes flags to return arrays containing both data and priority. Set extraction flags near the point of use and test the returned shape.

Priority queues are also consumed by extraction. Iterating or extracting to inspect contents can change what remains. If a diagnostic path, test helper, or logging method needs to inspect the queue without consuming the original, clone it first. That rule matters because disappearing work is a severe failure mode in schedulers.

Top-K Streams

A bounded heap is useful for top-K problems. If the program needs the ten largest scores from a large stream, it does not need to store and sort every score. It can keep a small heap of the best ten seen so far and discard values that cannot enter the result. The memory then grows with K, not with the full input size.

The same reasoning applies to search results, slowest requests, largest accounts, and highest-priority alerts. The result must still be verified against a full sort on small fixtures because heap code is easy to get backwards. If the heap keeps the wrong side of the comparison, the program may efficiently return the ten least relevant items.

Priority Versus Eligibility

Priority answers which eligible item should run first. Eligibility answers whether an item is allowed to run now. Retry systems often confuse these. A failed job with high priority should not necessarily run immediately if it has a backoff delay. A job scheduled for tomorrow should not run today just because it has a large priority number.

Keep eligibility time outside the priority queue or encode it as a separate stage. For example, a scheduler might first move due jobs into a ready queue, then use priority within ready jobs. That separation makes testing clearer: one test proves jobs are not eligible before their time, another proves eligible jobs are processed in priority order.

When Not To Use A Heap

If you need the complete sorted output once, sorting may be simpler and appropriate. If you need exact lookup by key, a map is a better structure. If you need FIFO fairness, a queue communicates the policy more directly. If the jobs must survive process failure, SplPriorityQueue alone is not enough because it is in-memory state.

Use a heap when the operation is truly about repeated access to the next priority item or bounded top-K selection. Do not introduce it merely because the word priority appears in a requirement. Sometimes priority is a database column used in an ORDER BY. Sometimes it is a business rule inside a durable queue. Sometimes it is a local algorithmic structure.

Verification

Test higher and lower priorities so the direction is unambiguous. Test ties so equal priority does not produce accidental behavior. Test negative priorities if the code uses them to adapt lower-is-better semantics. Test extraction flags because returned shape is part of the API. For top-K code, compare output with a full sort over small fixtures, including duplicates and fewer than K inputs.

Measure incremental workloads when performance is the reason for the heap. Compare repeated full sorting with heap insertion and extraction at realistic sizes. Also test inspection paths to confirm logging or debugging does not consume the live queue.

Operational Boundaries

A priority queue inside PHP is a local data structure. It is not a scheduler by itself. A scheduler also needs durable storage, a clock policy, worker coordination, observability, and recovery behavior. If the process exits, an SplPriorityQueue disappears with it. That is acceptable for an in-memory algorithm and unacceptable for business-critical jobs unless another component owns the durable state.

When priority decisions affect users, explain the policy in product terms. 100 and 10 are not meaningful by themselves. manual fraud review before marketing email, paid account before free account during outage, or oldest eligible retry before newest retry are policies that reviewers can challenge. The numeric priority should be an implementation of that policy, not the only place the policy exists.

Fairness deserves explicit attention. A pure max-priority queue can starve low-priority work if high-priority work keeps arriving. That may be correct for emergency alerts and wrong for normal customer processing. Systems that need fairness often combine priority with quotas, aging, separate queues, or round-robin scheduling. A heap can still be part of the implementation, but it should not hide the fairness rule.

Debuggability is another boundary. If an operator asks why a job ran before another job, the system should expose the priority inputs, eligibility time, tie-breaker, and extraction decision. A priority queue that is correct but opaque can still be painful to operate. Tests should therefore cover not only the extracted data, but also the diagnostic shape returned when extraction flags or wrapper methods expose priority details.

After this lesson, you should be able to explain why a heap maintains partial order, use SplPriorityQueue deliberately, define tie behavior, separate priority from eligibility, choose between a heap and a full sort, and verify top-K or scheduler behavior with fixtures that expose reversed comparisons and destructive iteration.