Thu May 29 09:19:10 PM +08 2025 #32 ✎

Ok, here is the trick in Python's heap structure implementation that allows us to cut amount of comparison when sifting up items in the heap. https://github.com/python/cpython/blob/3.13/Lib/heapq.py#L278 We don't compare parent value with the children when sifting it up, assuming that item which is taken from the leaf will end up somewhere near the leaf. The idea (D.Knuth, Art of Programming, Volume 3) is to sift item through smallest of the children (and shifting smallest child towards the root on each step) to the leaf without swapping it in a process, then assign it to the leaf, and then sift it down to the proper place. Doing it this way must reduce amount of "compare" operations, because sifting item down to it place from the leaf is shorter path than the sifting it up to its location towards the leaf. It is low price to don't stop ("break" the loop) on proper location, but go down to the leaf with low cost operations and then go a little bit up comparing values. I know I have formulated this idea twice already. :-) Here is the third time: we make long path cheaper, according the heuristics about nature of the value we are sifting through the heap. Now, here is my research. I had wrote a little bit of code in Rust, playing with the heap. I am 37 years old programmer, but never played with the heap data structure. Oh, boy, brothers. Just having some fun here. And I've tested and benchmarked some code. And... idk, but my benchmarks in Rust said that "non-optimized" version when we swapping items towards the leaf and breaking the loop when we arrived is faster. Is this compiler optimizations? Some low-level stuff? I am not really into that. Maybe I made a mistake. https://github.com/fuzz88/rust_stuff/blob/master/heap/src/main.rs#L73 test tests::bench_heapify_not_optimized ... bench: 2,796.01 ns/iter (+/- 54.45) test tests::bench_heapify_optimized ... bench: 6,668.45 ns/iter (+/- 182.72) Just a memo to myself: benchmark critical parts, make decisions based on the data. Or just use "good enough" stuff for the task. I will call it a day.