According to Tarjan[2] and Jensen et al.,[4] d-ary heaps were invented by Donald B. Johnson in 1975.
[1][5] Additionally, d-ary heaps have better memory cache behavior than binary heaps, allowing them to run more quickly in practice despite having a theoretically larger worst-case running time.
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.
In the upward-swapping procedure, each swap involves a single comparison of an item with its parent, and takes constant time.
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 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 for d = 2, and to for d = 3.
By using a d-ary heap with d = m/n, the total times for these two types of operations may be balanced against each other, leading to a total time of O(m logm/n n) for the algorithm, an improvement over the O(m log n) running time of binary heap versions of these algorithms whenever the number of edges is significantly larger than the number of vertices.