C10-Elementary-Data-Structures/problem.md
For each of the four types of lists in the following table, what is the asymptotic worst-case running time for each dynamic-set operation listed?
AnswerA 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.
AnswerActually we need not imitate the implementation of min-heap by array. And since we do not have A->last, it is not a big issue if the linked list is singly linked or doubly linked.
For unsorted linked list,
MAKE-HEAP: O(1).
MAKE-HEAP()
return MAKE-LINKED-LIST()
INSERT: O(1).
INSERT(A, x)
LIST-INSERT'(A->L, x)
MINIMUM: O(n). We need iterate the whole linked list.
MINIMUM(A)
return LIST-MINIMUM(A->L)
EXTRACT-MIN(A): O(n). Mainly due to MINIMUM.
EXTRACT-MIN(A)
x = LIST-MINIMUM(A->L)
LIST-DELETE(A->L, x)
return x
UNION: O(n). Since the linked lists here does not have L->last. We need O(n) to find the last element.
UNION(A, B)
A.last->next = B.first
For sorted linked list,
MAKE-HEAP: O(1). Nothing different.
MAKE-HEAP()
return MAKE-LINKED-LIST()
INSERT: O(n). We need find the position.
INSERT(A, x)
LIST-INSERT'(A->L, x)
MINIMUM: O(1).
MINIMUM(A)
return A->L.first
EXTRACT-MIN(A): O(1).
EXTRACT-MIN(A)
x = A->L.first
LIST-DELETE(A->L, A->L.first)
return x
UNION: O(n). Use algorithm like MERGE in merge sort.
UNION(A, B)
Merge(A, B)
In conclusion, we find
| Method | unsorted | sorted |
|---|---|---|
MAKE-HEAP() | O(1) | O(1) |
INSERT(A, x) | O(1) | O(n) |
MINIMUM(A) | O(n) | O(1) |
EXTRACT-MIN(A) | O(n) | O(1) |
UNION(A, B) | O(n) | O(n) |
Follow @louis1992 on github to help finish this task.