I've been playing with Binomial Heaps, and I encountered a problem I'd like to discuss here, because I think it may concern some user implementing a Binomial Heap data structure.
My aim is to have pointers to nodes, or handles, which directly points to Binomial Heap internal nodes, which in turn contain my priority value, which is usually an integer, when I insert them into a Binomial Heap.
In this way I keep the pointer/handle to what I have inserted, and if it's that the case, I can delete the value directly using binomial_heap_delete_node(node), just like an iterator works.
As we'll see, having this is NOT possible with Binomial Heaps, and that's because of the architecture of this data structure.
The main problem with Binomial Heaps, is that at some point you'll need an operation: binomial_heap_swap_parent_and_child(parent, child), and you'll need this operation in both binomial_heap_decrease_key(node, key) and in binomial_heap_delete_node(node). The purpose of these operations are quite clear, by reading their names.
So, the problem is how binomial_heap_swap_parent_and_child(parent, child) works: in all the implementations I saw, it swaps the priority value between nodes, and NOT the nodes themselves.
This will invalidate all of your pointers/handles/iterators to nodes, because they will still point to correct nodes, but those nodes won't have the same priority value you inserted before, but another one.
And this is quite logical, if we watch how Binomial Heaps (or Binomial Trees, in general) are structured: you have a parent node, treated by many children as "the parent", so many children points to it, but that parent node doesn't know how many children (or, more importantly, which children) are pointing to it, so it would be impossible to swap position of a node like this. Your only choice is to swap integer priority keys, but that will invalidate all pointers/handles/iterators to nodes.
NOTE: A possible solution would NOT be that instead of using binomial_heap_delete_node(node), one can just set priority of the node to remove to -999999999 (or such minimum values) and pop the minimum node out: this won't solve the problem, since binomial_heap_decrease_key(node, key) still needs the node parent-child swap operation, which the only solution is to swap integer priorities.
I want to know if someone has incurred in this problem before. I think the only solution is to use another heap structure, such as Binary Heap, Pairing Heap, or something else.
As with many data structure problems, it's not hard to solve this one with an extra level of indirection. Define something like:
struct handle {
struct heap_node *node; // points to node that "owns" this handle
struct user_data *data; // priority key calculated from this
}
You provide users with handles (either by copy or pointer/reference; your choice).
Each internal node points to exactly one handle (i.e. node->handle->node == node). Two such pointers are swapped to exchange parent and child.
Several variations are possible. E.g. the data field could be the data itself rather than a pointer to it. The main idea is that adding the level of indirection between handles and nodes provides the necessary flexibility.