CODEWITHSUNDEEP
algorithmdata-structures
Lily
Lily

Reputation: 99

Why d-heap is more useful for main memory than binary heap?

In the 2nd edition of M.A. Weiss: Data Structures and Algorithm Analysis in C, when I learn about binary heap and d-heap, there is description that when priority queue is too large to be loaded into the main memory completely, d-heap is very useful.

I think about the saying, in my opinion, when there are N elements, d-heap needs more pointers (about Nd) but has smaller height, and binary heap needs fewer pointers (about 2N) but has bigger height. So d-heap seems to need more space，after all, the height doesn't spend memory in my view. And if these two are completed by array not by pointer, these need the same N array cells. So I can not understand:
Why is d-heap more useful for main memory than binary heap?

Upvotes: 1

Views: 153

Answers (1)

Sneftel
Sneftel

Reputation: 41454

If you don't have room in memory for the whole queue, you'll need to load it in a piece at a time. Since that's a slow thing to do, the execution time will be dominated by the time you spend waiting to load the next thing in.

Let's suppose that it's a 4-way d-heap, and you only have enough room in RAM for two binary heap nodes, or one d-heap node. Which would you rather do: Descend through 10 levels of a d-heap, or 20 levels of a binary heap? Note that being able to store two binary heap nodes in memory won't really be useful: you only know which one you need to bring into RAM once you've looked at its parent. So with the binary heap you need to wait 19 times, and with the d-heap you need to wait 9 times.

Upvotes: 1

Related Questions