def _siftup(heap, pos):
endpos = len(heap)
startpos = pos
newitem = heap[pos]
# Bubble up the smaller child until hitting a leaf.
childpos = 2*pos + 1 # leftmost child position
while childpos < endpos:
# Set childpos to index of smaller child.
rightpos = childpos + 1
if rightpos < endpos and not heap[childpos] < heap[rightpos]:
childpos = rightpos
# Move the smaller child up.
heap[pos] = heap[childpos]
pos = childpos
childpos = 2*pos + 1
# The leaf at pos is empty now. Put newitem there, and bubble it up
# to its final resting place (by sifting its parents down).
heap[pos] = newitem
_siftdown(heap, startpos, pos)
There is possible another implemetations of siftup routine, withou calling _siftdown function. We need just on each iteration compare if value at pos index is bigger than children. If not we must break the loop, stop iteration.
Create two functions to heapify list, one using siftup which breaks the loop, another one using snippet I gave. Timeit and benchmark the best way possible agains both implementations, format the out put. give me the script
https://github.com/fuzz88/rust_stuff/blob/master/heap/bench.py
fuzz@workstation:~/code/rust_stuff/heap$ python bench.py
Heapify Performance Comparison (10 runs on list of 10,000 items):
With _siftdown: 0.030211 seconds
Without _siftdown: 0.011579 seconds
Result: Alternative implementation without _siftdown is faster.
🫠