March 19, 2026
Subtract first, sort faster
Monuses and Heaps
Subtract, don’t store: the math hack making heaps faster has devs buzzing
TLDR: A researcher suggests storing only differences (not full values) in heaps using a simple “partial subtraction” idea, promising cleaner search and sort. Commenters split: theorists applaud the elegant trick, skeptics demand benchmarks, and memers joke it’s just subtraction—important because it could simplify and speed up real-world data structures.
A mathy blog post just pitched a neat trick for faster searching and sorting: instead of storing the whole “weight” at every point in a data tree (a heap), only store the difference from the parent. The author frames it using a lightweight bit of algebra called a “monus” (think: subtraction that only works when it makes sense), but the community quickly turned it into a vibes check on elegant theory vs. real-world speed.
Fans are swooning over the simplicity. One early cheer declared it a “lovely bag of tricks,” and others compared it to delta-encoding—only keep the changes, not the whole thing. Math nerds piled on with links to related ideas like regular expression derivatives and differential dataflow, basically yelling “this rabbit hole goes deep.” But the skeptics arrived fast with the classic: “Cool story, where are the benchmarks?” A few rolled their eyes—“so… we’re subtracting now?”—while systems folks asked how it behaves under messy cases, like negative costs or weird ordering.
Meanwhile, the memes flew: “Subtraction DLC for your heap,” “It’s free real estate” for those saved weights, and an ELI5 hero explained it as “label kids by how much heavier they are than their parent.” Verdict? Equal parts hype and side-eye, with everyone asking if this tidy theory pays rent in production.
Key Points
- •The article introduces monus, an ordered monoid with a partial subtraction (∸), useful for algorithms with ordered weights.
- •It shows how the monus-defined order interprets x ≤ y via existence of a gap element z, and why this excludes groups with inverses.
- •Given total order (and commutativity, antisymmetry), a binary subtraction can be derived; this variant was used in the author’s graph search work (2021; 2025).
- •In heap-based algorithms, the heap property implies each child’s weight equals the parent’s weight combined with a nonnegative difference.
- •This leads to a difference-based heap representation that stores gaps rather than full weights, supporting operations like popMin and insert and enabling sorting.