File ListPriorityQueue.h

↰ Parent directory (ADS/priority)

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

Definition (ADS/priority/ListPriorityQueue.h)

Detailed Description

ListPriorityQueue is the lists of section 10.1.1: sorted, min() and deleteMin() in O( 1 ), insert() and decrease() in O( n ); unsorted, the other way round. The handle is the position of the cell.

The contracts [see File Contract.h]: min() and deleteMin() need a queue that is not empty, decrease() a handle of an item of this queue (checked in O( n ) with the invariants) and a priority not larger than its own; after deleteMin() no item has a smaller priority than the one removed; the invariant is that the list is sorted when it must be and that size() counts its cells. The operations are defined in ListPriorityQueue.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes