Heaping Up the Sky's Appointment Book

The ISS will cross my horizon in fourteen minutes. A NOAA weather bird follows eight minutes later. Then an amateur cubesat, then another station pass, then something Russian I can’t pronounce. My desk device tracks over forty objects, and each one has an opinion about when it deserves a chime.

The naive approach—scanning every satellite’s next-pass time whenever I need the soonest one—costs O(n) per query. With forty satellites and passes every few minutes, that’s tolerable. With four hundred, it’s not. The elegant solution is a priority queue, usually implemented as a binary heap: insert a pass in O(log n), extract the next one in O(log n), and the minimum always floats to the top like a buoy.

        [14:23 ISS]
       /          \
  [14:31 NOAA]   [14:45 SO-50]
    /      \
[15:02]   [15:19]

The heap property is simple: every parent is smaller (or larger, for a max-heap) than its children. Insertion bubbles up; extraction swaps the root with the last leaf and sifts down. Robert Floyd refined this into the elegant heapify algorithm in 1964, and by the 1980s heaps were the backbone of operating system schedulers, Dijkstra’s shortest-path algorithm, and every event-driven simulation worth running.

Clojure leans on its sorted collections. A sorted-set-by keeps passes ordered by time, and first peels off the next event:

(def passes (sorted-set-by #(compare (:aos %1) (:aos %2))))

(defn schedule [pass-queue pass]
  (conj pass-queue pass))

(defn next-pass [pass-queue]
  (first pass-queue))

(defn after-chime [pass-queue]
  (disj pass-queue (first pass-queue)))

Ada, designed for embedded systems and real-time avionics, treats this as serious infrastructure. The language’s strong typing means a pass time cannot accidentally become a frequency:

with Ada.Containers.Ordered_Sets;
use Ada.Containers;

type Satellite_Pass is record
   AOS  : Time;
   Name : String (1 .. 12);
end record;

function Earlier (L, R : Satellite_Pass) return Boolean is
   (L.AOS < R.AOS);

package Pass_Sets is new Ordered_Sets (Satellite_Pass, "<" => Earlier);

Pass_Queue : Pass_Sets.Set;

Ada’s Ordered_Sets give me the same logarithmic guarantees, but with compile-time proof that I haven’t confused a timestamp with a Doppler shift. In a system that wakes me at 3 a.m. for a decaying Starlink, I appreciate the guardrails.

The satisfying trick is that both implementations let me peek without removing—checking the next pass while the current one still chimes. When the ISS tone fades, I pop it, and NOAA surfaces without a scan. The sky stays sorted.

Priority queues are one of those structures that feel like overkill until you need them, and then they feel like gravity: obvious, inevitable, holding everything in its proper order. My desk hums with forty countdowns, and the heap decides which voice speaks next.