search

theodesp / go-heaps

Reference implementations of heap data structures in Go - treap, skew, leftlist, pairing, fibonacci
MIT License
97 stars 29 forks source link

Add decrease-key methods #5

Closed theodesp closed 6 years ago

theodesp commented 6 years ago

http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/pairing-heaps.pdf#page=4

theodesp commented 6 years ago

According to the original paper on pairing heaps, page 114, the decrease-key operation is implemented as follows. First, change the priority of the node whose key is to be decreased to have the new priority. If its priority is still greater than its parent (or if it's the root of the tree), you are done. Otherwise, cut the link from that node to its parent, then use the merge operation to combine the original heap with the subtree that was just cut from that tree.