File DaryHeap.h

↰ Parent directory (ADS/priority)

A d-ary heap of plain items, beyond the book: the heap of section 10.1 with D children per node in a vector, the children of the node i in the places :math:` D i + 1 , ldots , D i + D ` [see dary_child()], ordered by a predicate better( a , b ), true if a must come out before b.

Definition (ADS/priority/DaryHeap.h)

Detailed Description

The items are meant to be small and to carry their keys (e.g., f, g and a pointer to the node of a search), so that a comparison never follows a pointer; with D = 4 the heap is half as deep as a binary one, the four children of a node lie in one line of cache, and a push moves up half as many levels, at the price of D - 1 more comparisons per level on the way down. With BottomUp, pop() moves the hole of the root down to a leaf by the best children, D - 1 comparisons per level and none with the item that fills it, and then moves the last item up from there (the bottom-up heapsort of Floyd and Wegener): it pays when the last item, as in a heap full of stale copies, would go down to the bottom anyway, and loses when it stops halfway, as in the hold model of the simulations, where the default walk from the top stops as soon as the item fits.

There are no handles and no decrease-key: an item whose key improves is pushed again and the stale copy skipped (lazy deletion), which is what makes the items plain and the heap fast. The vector of a large heap is on huge pages [see File HugePageAllocator.h], so that the walk from the root to a leaf does not miss the TLB at each level and the vector, when it grows, is faulted in 2 MB at a time. HeapPriorityQueue [see File HeapPriorityQueue.h] is the realization with handles of the book.

The contracts [see File Contract.h]: D >= 2, top() and pop() need a heap that is not empty; the invariant is the order of the heap, no item better than its parent. The operations are defined in DaryHeap.tpp.

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

    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. Floyd, Algorithm 245: Treesort, Communications of the ACM 7(12), 701, 1964, doi:10.1145/355588.365103

  1. Wegener, BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small), Theoretical Computer Science 118(1), 81-98, 1993, doi:10.1016/0304-3975(93)90364-Y

  1. LaMarca, R. E. Ladner, The influence of caches on the performance of heaps, ACM Journal of Experimental Algorithmics 1, article 4, 1996, doi:10.1145/235141.235145

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes