Printable View
This is a question in my textbook, but I do not fully understand it, could anyone give me an explanation about this? Thx a lot!
Quote:
...We can perform BuildHeap in linear time for the leftist heaps by considering each element as one-node leftist heap, placing all these heaps on a queue and performing the following step, until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result...
Damn, that has more techie buzzwords than a hardware vendor's sales pitch. Well, not really, but it sure seems that way. :) Basically it says that you'll have a queue of heaps. You remove the first two heaps from the queue and merge them, then add the merged heap to the queue. Depending on your implementation, the queue could be an array or a linked list and the heaps could be arrays or linked lists. So you have the following combinations:
array of arrays
array of lists
list of arrays
list of lists
Without knowing it's hard to tell you how to do it, but here's some pseudocode that may help:
Code:while (size(heap) > 1) {
heap1 = dequeue(&heap);
heap2 = dequeue(&heap);
merged = merge(heap1, heap2);
enqueue(&heap, merged);
}
Haha, Thank u..:D