A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size \(n\) of these data structures?
Answer
(A)
Explanation
- P: link the tail of one list to the head of the other and update the tail pointer. That is a fixed number of pointer changes: \(\Theta(1)\).
- Q: copy both arrays into one array of size \(2n\) and run bottom-up build-heap, which takes linear time: \(\Theta(n)\). Inserting the \(n\) keys one at a time would cost \(\Theta(n \log n)\), so that bound (B, C) is not the best.
- R: an in-order traversal of each tree gives two sorted lists in \(\Theta(n)\). Merge them in \(\Theta(n)\), then build a BST from the merged list (middle element as root, recursively) in \(\Theta(n)\). Inserting one tree’s keys into the other would give the slower \(\Theta(n \log n)\) or \(\Theta(n^{2})\) of D and C.
Answer: A