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

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:

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

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

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

To merge two heaps:

- concatenate lists of roots
- compare the best roots to update a new best root

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

decrease priority of x:

- if x is a root:
- change the priority of x
- check if x is now the best root
- return

- if x.parent.flag = false:
- set x.parent.flag to true
- make x into a new root with the new priority
- return

- if x.parent.flag = true:
- promote x.parent into a new root
- set x.parent.parent.flag to true it not already a root
- 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