D-ary Heap - Analysis

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 log_d 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).

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:

,

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

,

for d = 2, and to

,

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. 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.