Advanced heaps

Question 1

Mergable heap methods (5 basic +2 extra)

Answer 1

Make-Heap, Insert, Minimum, Extract-Min, Union, Decrease-Key, Delete

Question 2

Binomial tree features (B(k)) (4 features)

Answer 2

1. Built out of two connected B(k-1) trees.
2. Has 2powk nodes.
3. Height of k.
4. At level I there are exactly (k i) nodes.

Question 3

Binomial heap definition

Answer 3

1. A group of binomial trees that maintain the heap property.
2. At most one binomial tree of a certain degree h.

Question 4

Binomial heap implementation

Answer 4

1. All the binomial trees roots point to the next one, where the first is the tree with the lowest degree, and last the highest.

Question 5

Binomial heap similarity

Answer 5

Binomial heaps are very similar to the binary counting system. The number of nodes directly corresponds to the binary counting system with correlation to k. Merging two heaps is same to adding to binary numbers.

Question 6

Binomial heap facts to know (2 facts)

Answer 6

1. the right tree of each node is a root of a tree of one level lower.
2. 0≤x.𝑑𝑒𝑔𝑟𝑒𝑒≤x.𝑝.𝑑𝑒𝑔𝑟𝑒𝑒−, the degree of a son node is always at least one less than the father node.

Question 7

Binomial heap union steps

Answer 7

1. Merge two BH to be one sorted linked list that includes all binomial trees.
2. Merge every two trees of the same degree until there is a maximum of one treefor a certain degree.

Question 8

Tree merging cases (4)

Answer 8

1. Current degree is different than next one (𝑥.𝑑𝑒𝑔𝑟𝑒𝑒≠𝑛𝑒𝑥𝑡−𝑥.𝑑𝑒𝑔𝑟𝑒𝑒) -> increment pointers.
2. x is first of a 3 same degree trees (𝑥.𝑑𝑒𝑔𝑟𝑒𝑒=𝑛𝑒𝑥𝑡−𝑥.𝑑𝑒𝑔𝑟𝑒𝑒=𝑛𝑒𝑥𝑡−𝑥.𝑠𝑖𝑏𝑙𝑖𝑛𝑔.𝑑𝑒𝑔𝑟𝑒𝑒) -> continue.
3. x is first of two same degree keys (𝑥.𝑑𝑒𝑔𝑟𝑒𝑒=𝑛𝑒𝑥𝑡−𝑥.𝑑𝑒𝑔𝑟𝑒𝑒≠𝑛𝑒𝑥𝑡−𝑥.𝑠𝑖𝑏𝑙𝑖𝑛𝑔.𝑑𝑒𝑔𝑟𝑒𝑒). and 𝒙.𝒌𝒆𝒚≤𝒏𝒆𝒙𝒕−𝒙.𝒌𝒆𝒚 -> merge them with x as root.
4. x is first of two same degree keys (𝑥.𝑑𝑒𝑔𝑟𝑒𝑒=𝑛𝑒𝑥𝑡−𝑥.𝑑𝑒𝑔𝑟𝑒𝑒≠𝑛𝑒𝑥𝑡−𝑥.𝑠𝑖𝑏𝑙𝑖𝑛𝑔.𝑑𝑒𝑔𝑟𝑒𝑒). and 𝒙.𝒌𝒆𝒚>𝒏𝒆𝒙𝒕−𝒙.𝒌𝒆𝒚 -> merge them with next-x as root.

Question 9

Binomial-Heap-Insert

Answer 9

Insert new Binomial tree and then merge

Question 10

Binomial-Heap-Extract-Min

Answer 10

Find smallest root (to return). Then for each child left add it as its own tree (in opposite order so that the sort is preserved) and merge all.

Question 11

Binomial-Heap-Decrease-Key

Answer 11

Increase the key and then bubble it up

Question 12

Binomial-Heap-Delete

Answer 12

Decrease key to -inf and remove minimum.

Question 13

Fibonacci heap (idea)

Answer 13

A linked list of trees. The pointer to the heap is the smallest root node. Each node has a degree field and a mark to specify if it has lost a child.

Question 14

Fibonacci heap (insert, min, union)

Answer 14

When inserting a new element, add the element as a new node. The minimum is pointed to by the heap so it’s easy to get the value. For union, just combine the two root lists but make sure to update the minimum pointer. All done in O(1).

Question 15

Fibonacci heap (extract min)

Answer 15

Take all the children nodes and add them to the root list. Then start merging trees with the same degree. The amortized cost is O(logn)

Question 16

Fibonacci heap (decrease key)

Answer 16

If the heap property Is affected, remove the node and it and its sub tree to the root list. Mark the parent, if it is already marked, add it to the root list as well. Do this recursively until reaching an unmarked node or the root of the tree. Amortized cost of O(1)