A mergeable heap supports the following operations MAKE HEAP (which creates an empty mergeable heap), INSERT, MINIMUM, EXTRACT MIN, and UNION 1 Show how to implement mergeable heaps using linked lists in each of the following cases Try to make each operation as efficient as possible Analyze the run...

In all three cases textMAKEHEAPMAKEHEAP simply creates a new list LL sets Lhead textNILLheadNIL and returns LL in constant time Assume lists are doubly linked To realize a linked list as a heap we ima ...

A mergeable heap supports the following operations: MAKE-HEAP (which creates an empty mergeable heap), INSERT, MINIMUM, EXTRACT-MIN,

Question:

A mergeable heap supports the following operations: MAKE-HEAP (which creates an empty mergeable heap), INSERT, MINIMUM, EXTRACT-MIN, and UNION.¹ Show how to implement mergeable heaps using linked lists in each of the following cases. Try to make each operation as efficient as possible. Analyze the running time of each operation in terms of the size of the dynamic set(s) being operated on.

a. Lists are sorted.

b. Lists are unsorted.

c. Lists are unsorted, and dynamic sets to be merged are disjoint.

Fantastic news! We've Found the answer you've been seeking!