Priority Search Queues: 1.5 dimensional Tree Search
summary
Implements Hinze’s priority-search penants as a Clojure library (psqlj) with a Java core using Adams weight-balanced trees and view-based decomposition, exposing get/assoc/dissoc/peak/pop/seek plus priority-bounded traversals. Claims: peak is constant-time storage of the winner; priority-bounded range query finds one low-priority entry in a 34,000-key range in ~27 microseconds vs ~150 milliseconds for a sorted-map composition — roughly three orders of magnitude. Library on GitHub/Clojars; benchmarks and mutable vs view implementations included.
AI-written summary · about
chapters (9)
- 0:00Introduction to PSQs
- 5:48Implementation approaches
- 8:12Halinsa's penant approach
- 10:22Alternative libraries
- 12:28The PSQLJ library
- 15:16Interface and usage
- 17:08Benchmarking results
- 23:33Technical deep dive
- 37:46Testing and future plans
related talks
16mResponsive Parallelism with Dynamic and First-Class Priorities
35mWhat Lies Beneath - A Deep Dive Into Clojure's Data Structures
34mHash Maps: more room at the bottom
29mPredicate Dispatch
15mSealing Pointer-Based Optimizations Behind Pure Functions
21mBonsai: Compiling Queries to Pruned Tree Traversals
20mThe Functional Essence of Imperative Binary Search Trees
14mFast Linear Programming through Transprecision Computing on Small and Sparse Data