]> git.lizzy.rs Git - rust.git/commit
BinaryHeap: Use full sift down in .pop()
authorUlrik Sverdrup <bluss@users.noreply.github.com>
Wed, 23 Dec 2015 02:57:48 +0000 (03:57 +0100)
committerUlrik Sverdrup <bluss@users.noreply.github.com>
Wed, 23 Dec 2015 03:07:36 +0000 (04:07 +0100)
commit52883ab843e90aff36008c2e77e0053c36509df8
tree8ffa2dceb501485573b68dd5cd49f979c33e1f91
parent42c3ef8f9fd4b0dd1f881c49323bad456163f202
BinaryHeap: Use full sift down in .pop()

.sift_down can either choose to compare the element on the way down (and
place it during descent), or to sift down an element fully, then sift
back up to place it.

A previous PR changed .sift_down() to the former behavior, which is much
faster for relatively small heaps and for elements that are cheap to
compare.

A benchmarking run suggested that BinaryHeap::pop() suffers
improportionally from this, and that it should use the second strategy
instead. It's logical since .pop() brings last element from the
heapified vector into index 0, it's very likely that this element will
end up at the bottom again.
src/libcollections/binary_heap.rs