Mutable access to the highest-priority element in a BinaryHeap

[moosingin3space]

The current implementation of BinaryHeap makes it difficult to write efficient I/O schedulers. I propose the addition of a function to BinaryHeap (inexact form):

fn peek_mut<F: FnOnce(Option<&mut T>)>(&mut self, func: F) {
    func(self.data.get(0));
    self.sift_down_to_bottom(0);
}

that would allow the caller to mutate the highest-priority element in the heap, then restore the heap property after the closure completes.

This functionality makes it much easier to build efficient priority-queue-based schedulers.

[sfackler]

Some discussion on #rust-libs: https://botbot.me/mozilla/rust-libs/2016-05-21/?msg=66470212&page=1

This is obviously implementable via pop-modify-push, but the idea here is to avoid the extra work involved in fixing up the heap after popping the element.

A closure-based API for this kind of thing is somewhat nontraditional. I would personally lean towards something like:

pub fn peek_mut<'a>(&'a mut self) -> Option<PeekMut<'a, T>> { ... }

pub struct PeekMut<'a, T> { ... }

impl<'a, T> Drop for PeekMut<'a, T> { ... }
impl<'a, T> Deref for PeekMut<'a, T> { ... }
impl<'a, T> DerefMut for PeekMut<'a, T> { ... }

where the Drop implementation re-heapifies. There are the obvious issues here around the semantics of forgeting the PeekMut - the closure based API was proposed to avoid that issue. Fortunately, BinaryHeap already has to deal with inconsistency issues that arise from comparison functions panicking during heapification. The results of querying the heap after such a panic will be inconsistent, but sound. I believe our rules around semantics after forgeting something that shouldn't be forgotten are the same.

cc @rust-lang/libs

[bluss]

The follow PR shows how much this algorithm can improve something implemented on top of it: rust-itertools/itertools#101 (and where we chose to hand roll the heap instead of using BinaryHeap, exactly for missing this API).

The Deref/Drop proposal works out well for this use case, if the PeekMut has an additional method that allows the modified element to be dequeued if needed:

impl<'a, T> PeekTop<'a, T> where T: Ord {
    fn remove(self) -> T {
        self.heap.swap_remove(0)
    }
}

Removing the top element also uses the sift down in drop afterwards, to put the swapped element in the right place.

[apasel422]

This has been implemented and stabilized.

[alexcrichton]

Yay!