use slotmap::{new_key_type, Key, SlotMap};
new_key_type! {
struct HeapKey;
}
#[derive(Copy, Clone)]
struct NodeHandle(HeapKey);
#[derive(Copy, Clone)]
struct Node<T> {
value: T,
children: [HeapKey; 2],
parent: HeapKey,
}
struct RandMeldHeap<T: Ord> {
sm: SlotMap<HeapKey, Node<T>>,
rng: std::num::Wrapping<u32>,
root: HeapKey,
}
impl<T: Ord + std::fmt::Debug> RandMeldHeap<T> {
pub fn new() -> Self {
Self {
sm: SlotMap::with_key(),
rng: std::num::Wrapping(0xdead_beef),
root: HeapKey::null(),
}
}
pub fn coinflip(&mut self) -> bool {
self.rng += (self.rng << 8) + std::num::Wrapping(1);
self.rng >> 31 > std::num::Wrapping(0)
}
pub fn insert(&mut self, value: T) -> NodeHandle {
let k = self.sm.insert(Node {
value,
children: [HeapKey::null(), HeapKey::null()],
parent: HeapKey::null(),
});
let root = self.root;
self.root = self.meld(k, root);
NodeHandle(k)
}
pub fn pop(&mut self) -> Option<T> {
self.sm.remove(self.root).map(|root| {
self.root = self.meld(root.children[0], root.children[1]);
if let Some(new_root) = self.sm.get_mut(self.root) {
new_root.parent = HeapKey::null();
}
root.value
})
}
pub fn remove_key(&mut self, node: NodeHandle) -> T {
let node = node.0;
self.unlink_node(node);
self.sm.remove(node).unwrap().value
}
pub fn update_key(&mut self, node: NodeHandle, value: T) {
let node = node.0;
self.unlink_node(node);
self.sm[node] = Node {
value,
children: [HeapKey::null(), HeapKey::null()],
parent: HeapKey::null(),
};
let root = self.root;
self.root = self.meld(node, root);
}
fn unlink_node(&mut self, node: HeapKey) {
let children = self.sm[node].children;
let parent_key = self.sm[node].parent;
let melded_children = self.meld(children[0], children[1]);
if let Some(mc) = self.sm.get_mut(melded_children) {
mc.parent = parent_key;
}
if let Some(parent) = self.sm.get_mut(parent_key) {
if parent.children[0] == node {
parent.children[0] = melded_children;
} else {
parent.children[1] = melded_children;
}
} else {
self.root = melded_children;
}
}
fn meld(&mut self, mut a: HeapKey, mut b: HeapKey) -> HeapKey {
if a.is_null() {
return b;
}
if b.is_null() {
return a;
}
if self.sm[a].value > self.sm[b].value {
std::mem::swap(&mut a, &mut b);
}
let ret = a;
let mut parent = a;
let mut trickle = b;
loop {
let children = self.sm[parent].children;
if children[0].is_null() {
self.sm[parent].children[0] = trickle;
self.sm[trickle].parent = parent;
break;
} else if children[1].is_null() {
self.sm[parent].children[1] = trickle;
self.sm[trickle].parent = parent;
break;
}
let c = self.coinflip() as usize;
let child = children[c];
if self.sm[child].value > self.sm[trickle].value {
self.sm[parent].children[c] = trickle;
self.sm[trickle].parent = parent;
parent = trickle;
trickle = child;
} else {
parent = child;
}
}
ret
}
pub fn len(&self) -> usize {
self.sm.len()
}
}
fn main() {
let mut rhm = RandMeldHeap::new();
let the_answer = rhm.insert(-2);
let big = rhm.insert(999);
for k in (0..10).rev() {
rhm.insert(k * k);
}
rhm.update_key(the_answer, 42);
rhm.remove_key(big);
while rhm.len() > 0 {
println!("{}", rhm.pop().unwrap());
}
}