d-heaps

• Binary heaps are so simple that they are almost always used when priority queues are needed.
• A simple generalization is a d-heap, which is exactly like a binary heap except that all nodes have d children (thus, a binary heap is a 2-heap).
• a d-heap is much shallower than a binary heap, improving the running time of inserts to O(logdN)
• for large d, the deleteMin operation is more expensive, because even though the tree is shallower, the minimum of d children must be found, which takes d − 1 comparisons using a standard algorithm. This raises the time for this operation to O(d logd N)
• If d is a constant, both running times are, of course, O(log N).
• Although an array can still be used, the multiplications and divisions to find children and parents are now by d, which, unless d is a power of 2, seriously increases the running time, because we can no longer implement division by a bit shift.
• d-heaps are interesting in theory, because there are many algorithms where the number of insertions is much greater than the number of deleteMins. They are also of interest when the priority queue is too large to fit entirely in main memory. In this case, a d-heap can be advantageous in much the same way as B-trees. Finally, there is evidence suggesting that 4-heaps may outperform binary heaps in practice.
• Merge


  The most glaring weakness of the heap implementation, aside from the inability to perform finds, is that combining two heaps into one is a hard operation.