File FibonacciHeapPriorityQueue.h

↰ Parent directory (ADS/priority)

The PRIORITYQUEUE [see File PriorityQueue.h] on a Fibonacci heap, the structure that section 11.5 names and does not describe: insert() and decrease() in O( 1 ) amortized time, deleteMin() in O( log n ), so that the algorithm of Fredman and Tarjan computes the shortest paths in O( m + n log n ).

Definition (ADS/priority/FibonacciHeapPriorityQueue.h)

Detailed Description

The heap is a collection of trees, each node not smaller than its parent, whose roots are in a circular list; the children of a node are in a circular list as well. insert() adds a tree of one node to the roots. deleteMin() moves the children of the minimum among the roots and then consolidates them, linking two roots of equal degree, the larger under the smaller, until all the degrees differ. decrease() cuts the node from its parent, if it became smaller than it, and makes it a root; a node that loses a second child is cut in turn (the cascading cut), so that a node of degree k has at least :math:` F_{k+2} geq phi^k ` descendants, :math:` phi = ( 1 + sqrt{5} ) / 2 , and the degrees are :math: O( log_phi n ) `.

Beyond the book, the nodes come from an ObjectPool [see File ObjectPool.h] of the heap, which takes back the node of deleteMin() for the next insert(), so that a node costs no call to the allocator and the nodes in use stay close in memory; the children of the minimum join the roots in O( 1 ), and the consolidation walks the roots where they are, with the trees by degree in an array on the stack (a degree is at most :math:` log_phi n < 64 `).

The contracts [see File Contract.h]: min(), minPriority() and deleteMin() need a heap that is not empty, decrease() a handle of a node of this heap (checked in O( n ) with the invariants) and a priority not larger than its own; the invariant is the order of the heap, the circular lists linked both ways, the parents, the degrees equal to the number of children, the roots not marked, the minimum among the roots and size() counting the nodes. On a heap of more than 1024 nodes it is checked on the roots only, so that a long sequence of operations at the level 3 stays linear. The operations are defined in FibonacciHeapPriorityQueue.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 11.5, https://algoritmicamente.it/materiali/libro/capitoli/cap11.pdf

    1. Fredman, R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM 34(3), 596-615, 1987, doi:10.1145/28869.28874

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes