"Martin v. Löwis" email@example.com wrote:
Paul Chiusano schrieb:
To support this, the insert method needs to return a reference to an object which I can then pass to adjust_key() and delete() methods. It's extremely difficult to have this functionality with array-based heaps because the index of an item in the array changes as items are inserted and removed.
It is not required. If you are careful, you can implement a pairing heap with a structure combining a dictionary and list. It requires that all values be unique and hashable, but it is possible (I developed one for a commercial project).
If other people find the need for it, I could rewrite it (can't release the closed source). It would use far less memory than the pairing heap implementation provided in the sandbox, and could be converted to C if desired and/or required. On the other hand, I've found the pure Python version to be fast enough for most things I've needed it for.