d-ary heap
The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2.[1][2][3] Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan[2] and Jensen et al.,[4] d-ary heaps were invented by Donald B. Johnson in 1975.[1]
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 as
Data structure
The d-ary heap consists of an
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 item x in the array is moved into its place, and the length of the array is decreased by one. Then, while item x and its children do not satisfy the heap property, item x is 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.[2][3]
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.[2][3]
To create a new heap from an array of n items, one may loop over the items in reverse order, starting from the item at position n − 1 and ending at the item at position 0, applying the downward-swapping procedure for each item.[2][3]
Analysis
In a d-ary heap with n items in it, both the upward-swapping procedure and the downward-swapping procedure may perform as many as logd n = log n / log d swaps. 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, is O(log n / log d). In the downward-swapping procedure, each swap involves d comparisons and takes O(d) time: it takes d − 1 comparisons 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, is O(d log n / log d).[2][3]
When creating a d-ary heap from a set of n items, most of the items are in positions that will eventually hold leaves of the d-ary tree, and no downward swapping is performed for those items. At most n/d + 1 items are non-leaves, and may be swapped downwards at least once, at a cost of O(d) time to find the child to swap them with. At most n/d2 + 1 nodes may be swapped downward two times, incurring an additional O(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
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:
- ,[8]
where sd(n) is the sum of all digits of the standard base-d representation of n and ed(n) is the exponent of d in the factorization of n. This reduces to
- ,[8]
for d = 2, and to
- ,[8]
for d = 3.
The space usage of the d-ary heap, 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.[2][7] 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.[2]
Applications
When operating on a
4-heaps may perform better than binary heaps in practice, even for delete-min operations.[2][3] Additionally, a d-ary heap typically runs much faster than a binary heap for heap sizes that exceed the size of the computer's
References
- ^ .
- ^ a b c d e f g h i j k l Tarjan, R. E. (1983), "3.2. d-heaps", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, pp. 34–38. Note that Tarjan uses 1-based numbering, not 0-based numbering, so his formulas for the parent and children of a node need to be adjusted when 0-based numbering is used.
- ^ ISBN 978-0-321-37013-6.
- ^ Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF), archived from the original (PDF) on 2007-06-09, retrieved 2008-02-05.
- ^ a b Tarjan (1983), pp. 77 and 91.
- ^ .
- ^ ISBN 978-3-540-28101-6.
- ^ .
- .
- ^ Kamp, Poul-Henning (11 June 2010), "You're doing it wrong", ACM Queue, 8 (6).