Michael Data

A [http://en.wikipedia.org/wiki/Heap_(data_structure) Heap] is a data structures which maintains a heap property.

binary heap

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 Tree

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))

d-ary heap

Generalization of the binary heap

Fibonacci heaps

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)

Construction

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.

Operations

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