Fibonacci heap

Fibonacci heap --- куча Фибоначчи.

A heap-ordered tree is a rooted tree containing a set of items, one item in each node, with the items arranged in a heap order: If [math]\displaystyle{ x }[/math] is any node, then the key of the item in [math]\displaystyle{ x }[/math] is no less than the key of the item in its parent [math]\displaystyle{ p(x) }[/math], provided [math]\displaystyle{ x }[/math] has a parent. The fundamental operation on heap-ordered trees is linking, which combines two item-disjoint trees into one. Given two trees with roots [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math], we link them by comparing the keys of the items in [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math]. If the item in [math]\displaystyle{ x }[/math] has the smaller key, we make [math]\displaystyle{ y }[/math] a child of [math]\displaystyle{ x }[/math]; otherwise, we make [math]\displaystyle{ x }[/math] a child of [math]\displaystyle{ y }[/math].

A Fibonacci heap (F-heap) is a collection of item-disjoint heap-ordered trees.