damn-fast-priority-queue
damn-fast-priority-queue copied to clipboard
Implement changes from @mfiano
https://gist.github.com/mfiano/3ddf2810cf8101f66009c3fdde8b020b
- The local swap functions are closing over state. Make them take the parent and left/right indices. To do this just return the left/right indices and wrap the callers in (setf parent-index ...).
- You can lexibind some aref lookups that are called multiple times, particular the parent, left, and right priority.
- In some various other places in the codebase, you can also lexibind the aref calls that are called more than once. I forget where though.
Also read-eval (ash 1 64) just to be sure it's a constant for implementations that don't do constant folding for whatever reason.
Also see the benchmark at https://github.com/jdz/simple-pairing-heap/blob/master/bench.org