File IndexedDaryHeap.h

↰ Parent directory (ADS/priority)

A d-ary heap of the integers [ 0 , n ) with keys and decrease-key, beyond the book: the heap of DaryHeap [see File DaryHeap.h], whose items are the pairs ( key , id ) with the key inline, so that a comparison never leaves the heap, and a vector of the places of the ids, which takes the place of the handles of HeapPriorityQueue [see File HeapPriorityQueue.h].

Definition (ADS/priority/IndexedDaryHeap.h)

Detailed Description

The children of the place i are :math:` D i + 1 , ldots , D i + D ` and its parent :math:` lfloor ( i - 1 ) / D rfloor , so that a heap of s items has height :math: lceil log_D ( ( D - 1 ) s + 1 ) rceil `; push() and decrease() move up at most that many levels, one comparison each, and pop() moves down as many with D comparisons each: :math:`[

T_{mathrm{push}} , T_{mathrm{decrease}} = O( log_D s ) , qquad T_{mathrm{pop}} = O( D log_D s ) ,

` which for Dijkstra’s and Prim’s algorithms, m decreases and n pops, gives :math:` O( m log_D n + n D log_D n ) , least near :math: D = m / n ` (Johnson). With D = 4 a pop() reads the four children of a node in half a line of cache when the keys are 32-bit integers, the choice that Larkin, Sen and Tarjan found the fastest in practice; the space is :math:` ( 4 + k ) s + 4 n ` bytes, k the size of a key. It is a PRIORITYQUEUE of section 10.1 [see File PriorityQueue.h], the ids its items and their own handles, so that the algorithms of the book that take a priority queue run on it [see File ShortestPaths.h, File MinimumSpanningTree.h].

The contracts [see File Contract.h]: the ids are in [ 0 , n ), push() needs an id not in the heap, decrease() one in the heap and a key not greater than its own, top() and pop() a heap that is not empty; the invariant is the order of the heap, no key less than that of the parent, with the places of the ids in their vector. The operations are defined in IndexedDaryHeap.tpp.

    1. Johnson, Priority queues with update and finding minimum spanning trees, Information Processing Letters 4(3), 53-57, 1975, doi:10.1016/0020-0190(75)90001-0

    1. Larkin, S. Sen, R. E. Tarjan, A back-to-basics empirical study of priority queues, Proceedings of ALENEX, 61-72, 2014, doi:10.1137/1.9781611973198.7

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/priority/impl/IndexedDaryHeap.tpp

  • cstddef

  • vector

Namespaces

Classes