File LinkedHeapPriorityQueue.h

↰ Parent directory (ADS/priority)

The PRIORITYQUEUE [see File PriorityQueue.h] on a heap realized as a binary tree with pointers, beyond the book, instead of the vector of section 10.1: the nodes are those of a complete binary tree numbered by levels from 1, and the path from the root to the node k follows the bits of k after the leading one, 0 to the left and 1 to the right, so that the last leaf, where insert() adds a node and from where deleteMin() takes the one that replaces the root, is found in :math:` O( log n ) ` steps.

Definition (ADS/priority/LinkedHeapPriorityQueue.h)

Detailed Description

The items move up and down by swapping the contents of the nodes, as in the heap on a vector, and each operation takes :math:` O( log n ) ` time.

With L = true the heap keeps instead a pointer to the last leaf, and finds the place of the next one by walking the tree: the new leaf is the right sibling of the last one if this is a left child; otherwise one goes up while on a right child, then, unless at the root, to the right sibling, and down along the left children to a leaf, whose left child is the new leaf (from the root this starts a new level). After deleteMin() the new last leaf is found symmetrically: the left sibling of the old one if this was a right child; otherwise up while on a left child, to the left sibling unless at the root, and down along the right children. Both walks take :math:` O( log n ) ` steps, and need no counter of the nodes.

The nodes come from an ObjectPool [see File ObjectPool.h] of the queue, which takes back the node of deleteMin() for the next insert(), so that a node costs no call to the allocator.

The contracts [see File Contract.h]: min(), minPriority() and deleteMin() need a queue that is not empty; after deleteMin() no item has a smaller priority than the one removed; the invariant is the order of the heap, the parents, and the shape, i.e., the node k has the children 2 k and 2 k + 1 exactly when they are at most size(), and with L the pointer is the node size(). On a heap of more than 1024 nodes only the root and the last leaf are checked, so that a long sequence of operations at the level 3 stays linear. The operations are defined in LinkedHeapPriorityQueue.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes