Created: 2023-04-02T00:42:17-05:00
This card pertains to a resource available on the internet.
Heap property: no element is smaller than its parent
Priority Queue: stores nodes sorted by key, with the lowest/highest key always at the front of the queue.
Get Min: Retrieve lowest key in tree.
Extract Min: Remove lowest key from tree and rebalance the queue.
Insert: Put a new element in the queue.
Decrease Key: Raise the priority of an element already in the queue.
Degree: how many children are beneath a given node.
Binomial Tree: when trees are created by attaching sub-trees of identical sizes.
"Root list" stores all of the tree nodes which are siblings of the parent. The heap has an implicit parent all initial nodes belong to.
Each node also has a downward and upward pointer.
Get Min: store a pointer to the lowest node, so this is O(1)
Insert: Add a new tree with the new element; update minimum pointer if smaller
Extract Min: Must walk root set to find next minima; so use the opportunity to rebalance the root trees.
Merge tree: attach node with larger key as a child of one with a smaller key.
Cut that particular node from its parent, modify the key, and insert it to the root set. Update pointer to the minimum node if its outdated. Future ExtractMin calls will rebalance the tree and fold the grafted tree back where it belongs--eventually.
"Cut at most one child per node."
If cutting the node causes the parent to lose only one child in total, the parent nodes are also cut. This recurses for each parent node that has its total depth reduced by exactly one due to a removal operation.
Cut nodes are rebalanced in the next ExtractMin.