how does this approach deal with mutabiliy? if we have multiple keys a, and change one key from a to b and later back to a, we loose any information about the original position. we could simply define this sequence as undefined or interpret `update' as `insert' ...
I think that updating an object gives would have the same meaning as erasing the object and then re-pushing it. The heap shouldn't expect to retain a history of previous values.
Another option would be chaining, where each heap node contains either a single item or a linked list of items with the same key value.
chaining would be a reasonable way for node-based implementations, but not for container adaptors ...
I'm not sure that's entirely true. Obviously, it won't work for any containers of the form container<T> where T is the value type of the heap. If you can rebind it to something like container<node<T>>, you might be able to make it work. Chaining can change the properties of the data structure, however. For example, a binary heap (for example) using array<T, N> does not require an allocator. A stable binary heap (using chaining) would require allocations. For node-based heaps, this is, of course, a non-issue. Andrew