File MinMaxHeap.h

↰ Parent directory (ADS/priority)

Two double-ended priority queues of plain items, beyond the book: the best and the worst item by better( a , b ) (a before b) both at hand, both removable in :math:` O( log n ) ` time.

Definition (ADS/priority/MinMaxHeap.h)

Detailed Description

  • MinMaxHeap is the min-max heap of Atkinson, Sack, Santoro and Strothotte: a binary heap in a vector whose levels alternate, the even ones (the root’s) ordered for the best item and the odd ones for the worst, so that a node of an even level is not worse than any item of its subtree and one of an odd level not better. The best item is the root, the worst the worse of its two children. A push moves the item to the right kind of level by at most one swap with its parent and then up by grandparents; a removal moves the last item down from the root (or from the child) by the best (worst) of the up to 4 grandchildren and 2 children: :math:` lfloor log_2 n rfloor + 1 ` comparisons up and about :math:` 1.5 log_2 n ` down per level pair;

  • IntervalHeap is the interval heap of van Leeuwen and Wood: the items two by two in the nodes of a complete binary tree, each node an interval [ lo , hi ] (lo not worse than hi) contained in the interval of its parent, so that the lo of the nodes are a heap for the best and the hi a heap for the worst; the root holds the best and the worst item. A tree of half the height of a binary heap, each level of a walk two comparisons at most, and the two items of a node in one line of the cache: about :math:` log_2 ( n / 2 ) ` levels for a push and a removal, faster in practice than the min-max heap.

A run of removals with no push, as long as an eighth of the items and 64 at least, sorts the items once (by the radix sort for the numbers and the pairs of numbers in the order of std::less or std::greater [see File OrderKey.h]), so that the rest of the run takes them from the two ends of the sorted array in O( 1 ) time each, as a balanced tree does; the next push makes the array a heap again in O( n ) time (an interval heap straight from the sorted items, the node j holding the j-th best and the j-th worst; a min-max heap by the construction from the bottom up of Atkinson et al.). Both costs are paid by the run, :math:` O( log n ) ` amortized per removal.

The contracts [see File Contract.h]: min(), max(), popMin() and popMax() need a queue that is not empty; the invariant, checked on queues of at most 1024 items, is the order of the levels (the intervals). The operations are defined in MinMaxHeap.tpp.

    1. Atkinson, J.-R. Sack, N. Santoro, T. Strothotte, Min-max heaps and generalized priority queues, Communications of the ACM 29(10), 996-1000, 1986, doi:10.1145/6617.6621

  1. van Leeuwen, D. Wood, Interval heaps, The Computer Journal 36(3), 209-216, 1993, doi:10.1093/comjnl/36.3.209

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes