Implement append for BinaryHeap #32526
Description
This can be done in O(n + m) time by appending the underlying vectors and then using the build heap algorithm in the From<Vec<T>> impl. Note that in some circumstances this will perform worse than repeatedly pushing (as is done in h1.extend(h2)), because the time complexity of that approach is O(m log (m + n)). In both approaches, append should ensure that the larger of the two heaps acts as the "destination" of the merge in order to move as few elements as possible.
append should use a heuristic to determine which approach to take. This should be based on the sizes of the two heaps, but may also incorporate the vectors' capacities.
Pseudo-code:
use std::mem::swap;
fn shouldMergeWithBuildHeap<T>(v1: &Vec<T>, v2: &Vec<T>) -> bool { ... }
impl<T: Ord> BinaryHeap<T> {
pub fn append(&self, other: &mut Self) {
if other.is_empty() {
return;
}
if self.is_empty() {
swap(self, other);
return;
}
if self.len() < other.len() {
swap(self, other);
}
if shouldMergeWithBuildHeap(&self.data, &other.data) {
self.data.append(&mut other.data.append);
self.build_heap();
} else {
self.extend(other.drain());
}
}
fn build_heap(&mut self) {
let mut n = self.len() / 2;
while n > 0 {
n -= 1;
self.sift_down(n);
}
}
}For now, a simple version that just extends the smaller one into the larger one could suffice:
impl<T: Ord> BinaryHeap<T> {
pub fn append(&self, other: &mut Self) {
if other.is_empty() {
return;
}
if self.is_empty() {
swap(self, other);
return;
}
if self.len() < other.len() {
swap(self, other);
}
self.extend(other.drain());
}
}