Michael's Wiki

A special case of the d-ary heap where $d=2$. “Simple and fast”, in that it has a low constant factor in its O-notation. Uses log(n) time for all operations except construction from an existing set of n items, which takes O(n) time.

[http://en.wikipedia.org/wiki/Binary_heap Binary heaps] are implicit data structures. The logical structure is just an array of items, but the key information that makes it a binary heap is in the ordering within that array.

Can be represented as an implicit tree with n nodes (items). For each non-root node x, priority(parent(x)) \leq priority(x).

Implicit complete binary tree: An array A of n items which are interpreted as a tree.

• * children(array[i]) = array[2i+1] , array[2i+2]
• * parent(array[i>0]) = array[floor( (i-1)/2)]

• min():
• return A[0]
• min operation is O(1)
• delete_min():
• move item in A[n-1] to A[0]
• bubble_down(0)
• add(x):
• Need a dynamic array which can be expanded
• Add the item to the end of the array
• bubble_up(n-1)
• bubble_down(g):
• while A[g] is larger than either of its children:
• swap A[g] and g with its smallest child
• bubble_up(g):
• while parent(A[g]) > A[g]:
• swap A[g] and g with its parent
• the bubble procedures are O(log(n))

Generalization of the binary heap

Advantages over binary or k-ary heaps:

• * Good O-notation
• O(1) to decrease priority
• O(log n) to delete minimum value
• * Allows merge operations
• But known good applications of merge… ?

Disadvantages:

• * Large constant factors hidden in space and time O-notation
• Not practical
• * space and time bounds rely on amortization, so has bad worst-cases

Overall structure is a forest of heap-ordered trees and a pointer to the best (least-priority) tree root. No a priori constraints on trees, but the data structure operations will only cause certain shapes to occur.

Memory use:

• * One node object per data item
• data item and its priority
• pointer to parent node or null pointer if root
• pointer to a child node (or null if leaf)
• number of children
• pointers to left and right nodes, in circular doubly-linked list of siblings or roots
• boolean flag for [(not root) && (one of its children has been removed after this node became non-root)]
• If the flag is set, then the node can't have a child deleted from it

Potential function: $\phi$ = (# trees) + 2(# true flags)

For n items:

1. create a new tree root for each item and link the roots together

#* actual time O(n) and $\Delta \phi = +n$ ; total O(n)

Also maintain a data structure which points to node objects given the node value, like a hash table.

The tricky operations are deletion and decrease-priority.

To insert a new item:

1. create a new tree root and link it in
2. compare with previous best root, update if necessary

#* actual time O(1), $\Delta \phi = +1$ ; total O(1)

To merge two heaps:

1. concatenate lists of roots
2. compare the best roots to update a new best root

#* actual time O(1), $\Delta \phi = 0$ ; total O(1)

decrease priority of x:

1. if x is a root:
   1. change the priority of x
   2. check if x is now the best root
   3. return
2. if x.parent.flag = false:
   1. set x.parent.flag to true
   2. make x into a new root with the new priority
   3. return
3. if x.parent.flag = true:
   1. promote x.parent into a new root
   2. set x.parent.parent.flag to true it not already a root
   3. recursively make roots of ancestors with true flags

$\phi$ = (# trees) + 2(# true flags) If $k$ is the number of promotions made during the call:

• * actual time = O(k+1)
• * $\Delta \phi$ from new tree roots = +k
• * $\Delta \phi$ from flag going true to false = -2(k-1)
• * $\Delta \phi$ from flag going false to true = +2
• * Total time = $k + k - 2k + 1 + 2 +2 = +5$

to delete-min:

• * Have to merge the list of children of the deleted node into the list of roots.
• easy
• * Have to find the new best tree root
• easy but slow
• * Have to improve the structure of the forest in order to reduce the potential function

• delete-min():
• promote children of the deleted node into roots
• while any two trees T1 and T2 have the same number of children:
• compare the priorities of their roots to make one root the child of the other
• Or:
• allocate array C[(max # children +1) of tree roots] initially empty
• make collection R of tree roots not yet in C
• while R is nonempty:
• find and remove X from R
• if C[X.numchildren] is nonempty:
• merge C with C[X.numchildren] and store the result back in R
• else:
• add X to C[X.numchildren]

• * Actual time = t = initial number of trees before the merge.
• * $\Delta \phi$ = (new # trees) - (old # trees)
• Maximum number of new trees is ⇐ (max # children of new roots) - t
• * total = O(max # children of new roots)

• define F(i) = min # of nodes in a tree or subtree of a fibonacci heap whose root as i children
• a tree with zero children has at least 1 node in it
• a tree with one child has at least 2 nodes in it
• a tree with two children has at least 3 nodes in it
• a tree with three children has at least 4 nodes in it
• In a Fibonacci heap, F(i) follows the Fibonacci sequence.
• So delete-min takes amortized log(n) time