d-ary heap

Thed-ary heapord-heapis apriority queuedata structure,a generalization of thebinary heapin which the nodes havedchildren instead of 2.Thus, a binary heap is a 2-heap, and aternary heapis a 3-heap. According to Tarjanand Jensen et al.,d-ary heaps were invented byDonald B. Johnsonin 1975.

This data structure allows decrease priority operations to be performed more quickly than binary heaps, at the expense of slower delete minimum operations. This tradeoff leads to better running times for algorithms such asDijkstra's algorithmin which decrease priority operations are more common than delete min operations.Additionally,d-ary heaps have bettermemory cachebehavior than binary heaps, allowing them to run more quickly in practice despite having a theoretically larger worst-case running time.Like binary heaps,d-ary heaps are anin-place data structurethat uses no additional storage beyond that needed to store the array of items in the heap.

Data structure

Thed-ary heap consists of anarrayofnitems, each of which has a priority associated with it. These items may be viewed as the nodes in a completed-ary tree, listed inbreadth first traversal order:the item at position 0 of the array (usingzero-based numbering) forms the root of the tree, the items at positions 1 throughdare its children, the nextd²items are its grandchildren, etc. Thus, the parent of the item at positioni(for anyi> 0) is the item at position⌊(i− 1)/d⌋and its children are the items at positionsdi+ 1throughdi+d.According to theheap property,in a min-heap, each item has a priority that is at least as large as its parent; in a max-heap, each item has a priority that is no larger than its parent.

The minimum priority item in a min-heap (or the maximum priority item in a max-heap) may always be found at position 0 of the array. To remove this item from the priority queue, the last itemxin the array is moved into its place, and the length of the array is decreased by one. Then, while itemxand its children do not satisfy the heap property, itemxis swapped with one of its children (the one with the smallest priority in a min-heap, or the one with the largest priority in a max-heap), moving it downward in the tree and later in the array, until eventually the heap property is satisfied. The same downward swapping procedure may be used to increase the priority of an item in a min-heap, or to decrease the priority of an item in a max-heap.

To insert a new item into the heap, the item is appended to the end of the array, and then while the heap property is violated it is swapped with its parent, moving it upward in the tree and earlier in the array, until eventually the heap property is satisfied. The same upward-swapping procedure may be used to decrease the priority of an item in a min-heap, or to increase the priority of an item in a max-heap.

To create a new heap from an array ofnitems, one may loop over the items in reverse order, starting from the item at positionn− 1and ending at the item at position 0, applying the downward-swapping procedure for each item.

Analysis

In ad-ary heap withnitems in it, both the upward-swapping procedure and the downward-swapping procedure may perform as many aslog_dn= logn/ logdswaps. In the upward-swapping procedure, each swap involves a single comparison of an item with its parent, and takes constant time. Therefore, the time to insert a new item into the heap, to decrease the priority of an item in a min-heap, or to increase the priority of an item in a max-heap, isO(logn/ logd).In the downward-swapping procedure, each swap involvesdcomparisons and takesO(d)time: it takesd− 1comparisons to determine the minimum or maximum of the children and then one more comparison against the parent to determine whether a swap is needed. Therefore, the time to delete the root item, to increase the priority of an item in a min-heap, or to decrease the priority of an item in a max-heap, isO(dlogn/ logd).

When creating ad-ary heap from a set ofnitems, most of the items are in positions that will eventually hold leaves of thed-ary tree, and no downward swapping is performed for those items. At mostn/d+ 1items are non-leaves, and may be swapped downwards at least once, at a cost ofO(d)time to find the child to swap them with. At mostn/d²+ 1nodes may be swapped downward two times, incurring an additionalO(d)cost for the second swap beyond the cost already counted in the first term, etc. Therefore, the total amount of time to create a heap in this way is

$\sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).$

The exact value of the above (the worst-case number of comparisons during the construction of d-ary heap) is known to be equal to:

${\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n{\bmod {d}}))\left(e_{d}\left(\left\lfloor {\frac {n}{d}}\right\rfloor \right)+1\right)$,

where s_d(n) is the sum of all digits of the standard base-d representation of n and e_d(n) is the exponent of d in the factorization of n. This reduces to

$2n-2s_{2}(n)-e_{2}(n)$,

for d = 2, and to

${\frac {3}{2}}(n-s_{3}(n))-2e_{3}(n)-e_{3}(n-1)$,

for d = 3.

The space usage of thed-aryheap, with insert and delete-min operations, is linear, as it uses no extra storage other than an array containing a list of the items in the heap.If changes to the priorities of existing items need to be supported, then one must also maintain pointers from the items to their positions in the heap, which again uses only linear storage.

Applications

When operating on agraphwithmedges andnvertices, bothDijkstra's algorithmforshortest pathsandPrim's algorithmforminimum spanning treesuse a min-heap in which there arendelete-min operations and as many asmdecrease-priority operations. By using ad-ary heap withd=m/n,the total times for these two types of operations may be balanced against each other, leading to a total time ofO(mlog_m/nn)for the algorithm, an improvement over theO(mlogn)running time of binary heap versions of these algorithms whenever the number of edges is significantly larger than the number of vertices.An alternative priority queue data structure, theFibonacci heap,gives an even better theoretical running time ofO(m+nlogn),but in practiced-ary heaps are generally at least as fast, and often faster, than Fibonacci heaps for this application.

4-heaps may perform better than binary heaps in practice, even for delete-min operations.Additionally, ad-ary heap typically runs much faster than a binary heap for heap sizes that exceed the size of the computer'scache memory: A binary heap typically requires morecache missesandvirtual memorypage faultsthan ad-ary heap, each one taking far more time than the extra work incurred by the additional comparisons ad-ary heap makes compared to a binary heap.

External links

• C++ implementation of generalized heap with D-Heap support