This is the foundations page. The parent note throws around a pile of vocabulary — priority, insert, extract-min, peek, growth symbols like O(logn), and the words FIFO, LIFO, plus a few we will define in their own sections below. If any of those made you pause, start here. We build each one from zero, anchor it to a picture, and say why the topic needs it — in an order where each idea rests on the one before, so nothing is used before it is explained.
Before "priority", before "queue", there is just the idea of a collection — a bag that holds items.
Figure — a rectangular container holds four labelled boxes A, B, C, D floating in no particular order. The caption underneath stresses that we can add and remove, but the rule for "who leaves next" is still undecided.
Why the topic needs it: a priority queue is a collection plus one rule ("most important leaves next"). You can't understand the rule until you can see the bag it governs.
A collection becomes useful the moment we fix a rule for who leaves next. There are exactly three rules you must be able to tell apart.
Figure — three panels share the same items A, B, C. Left (cyan): a FIFO queue with an amber arrow showing A leaving first (earliest arrival). Middle: a LIFO stack with C leaving first (latest arrival, taken off the top). Right: a min-priority queue where the badges read p=5, p=2, p=8 and the amber arrow pulls out B (p=2, the smallest) first, ignoring arrival order entirely.
Why the topic needs it: the word "queue" in "priority queue" is misleading. Look at the right-hand panel — the priority queue does not obey the arrival order; it picks B because its priority is smallest. Knowing all three rules is the only way to see clearly what a priority queue is not.
Most often p is just a number, and numbers are easy to compare. But the only thing a priority really needs is a total order — a rule that, given any two labels, tells you which comes first (with no ties left undecided).
Why the topic needs it: priority is the whole point. Without a comparable label there is nothing to sort by, and "most important next" is meaningless. Real programs use strings, timestamps and custom objects as priorities all the time — numbers are just the easiest example to draw.
A collection is only defined by what you can do to it. For a priority queue there are exactly three actions.
Figure — a central box labelled "priority queue" holds three items stacked with B (p=2) at the top in amber marked "top = winner", then A (p=5) and C (p=8) below. A cyan arrow on the left labelled insert(x, p) feeds an item in. An amber solid arrow on the right pulls B out (extract-min → B: remove AND return). A white dashed arrow below it labelled peek → B only looks — the item stays inside.
Why "and return"?extract does two jobs at once: it removes the winner from the collection and hands it back to you. peek does only the "look" half — the item stays inside.
Why the topic needs it: these three verbs are the priority queue's contract — and a contract must say what happens at its boundary. An algorithm like Dijkstra loops while queue not empty, so knowing the empty behaviour is what makes the loop terminate safely.
The parent note calls a priority queue an ADT. This word trips people up, so we build it slowly.
Why "abstract"? Because we promise behaviour only. This is powerful: you can write Dijkstra's algorithm using only the PQ contract, then later swap in a fast Heap without changing a line of the algorithm.
Why the topic needs it: the parent note keeps saying "a heap is just one way to build it". That sentence only makes sense once you accept that the priority queue is the contract and the heap is the machine fulfilling it.
The parent note compares implementations using O(1), O(n), O(logn). Here is that language from zero.
O(1) — constant: the work does not depend on n at all. Doubling n changes nothing. Picture: grabbing the top plate — same effort with 5 plates or 5000.
O(n) — linear: work grows in step with n. Doubling n doubles the work. Picture: scanning every item once to find the smallest.
O(logn) — logarithmic: work grows very slowly. Doubling n adds just one extra step. Picture: the number of times you can halve n before reaching 1.
Figure — three curves on axes "n (number of items)" vs "work (steps)". A flat cyan line at height 1 is O(1). An amber curve rising slowly is O(log n), with an annotation "doubling n adds one step". A straight white diagonal is O(n), annotated "doubling n doubles work". The picture makes visible that the amber log curve stays far below the white linear line as n grows.
Why the topic needs it: the whole reason heaps exist is a speed argument. Without Big-O you cannot see why O(logn) per operation crushes O(n) per operation when you do millions of operations. This is the payoff line of the parent note.
The parent note warns that PQs are not stable. One last piece of vocabulary.
Why the topic needs it: real schedulers must break ties predictably. The pair (p,seq) is the standard trick, and you need to understand pairs as compound priorities to read it.
Here is how every idea above stacks up into the topic. Read it top-down: the boxes at the top are the raw ingredients (a collection, a comparable priority), the middle row shows the three order-out rules and the operations they enable, and every arrow means "is needed to understand". Follow any path of arrows down to the bottom box Priority Queue — that path is exactly the reading order of this page. If a box feels shaky, jump back to its section before continuing.
Trace one path as a check: Collection → Order-out rule → Priority order → Operations → Priority Queue. Reading those five boxes in order gives you the shortest honest definition of the topic. The side branches (FIFO/LIFO for contrast, Big-O for the speed argument, the empty case and tie-breaking for the boundaries) fill in why each choice matters.
