File HeapPriorityQueue.h

↰ Parent directory (ADS/priority)

The PRIORITYQUEUE [see File PriorityQueue.h] on a heap.

Definition (ADS/priority/HeapPriorityQueue.h)

Detailed Description

HeapPriorityQueue is the heap of section 10.1.3, a vector H of capacity n holding a d-ary tree that is full but for the rightmost leaves of the last level, each node not smaller than its parent: the children of the place i are :math:` d i + 1 , ldots , d i + d ` and its parent is :math:` lfloor ( i - 1 ) / d rfloor ` (with d = 2, l( i ) = 2 i + 1, r( i ) = 2 i + 2, p( i ) = :math:` lfloor ( i - 1 ) / 2 rfloor ). insert() and decrease() move the item up, deleteMin() moves the last leaf down from the root [see minHeapRestore()], in :math: O( log_d n ) ` and :math:` O( d log_d n ) ` time; each item knows its place, kept by swap(), and so the handle finds it (exercise 10.6 for d > 2). Beyond the book, the items come from an ObjectPool [see File ObjectPool.h] of the queue, which takes back the item of deleteMin() for the next insert(), so that an item costs no call to the allocator and the items in use stay close in memory.

The contracts [see File Contract.h]: min(), minPriority() and deleteMin() need a queue that is not empty, insert() one that is not full, and decrease() a handle of an item of this queue and a priority not larger than its own; the invariant, checked at level 3 in O( n ) time, is the order of the heap together with the places that the items remember. On a heap of more than 1024 items only the root and the last item are checked, so that a long sequence of operations at the level 3 stays linear. The operations are defined in HeapPriorityQueue.tpp.

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

      1. Williams, Algorithm 232: Heapsort, Communications of the ACM 7(6), 347-348, 1964, doi:10.1145/512274.512284

    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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes