Exams › GATE › Technical

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 the meld operation on instances of size `n` of these data structures?

1. P: Θ(1), Q: Θ(n), R: Θ(n)
2. P: Θ(1), Q: Θ(n log n), R: Θ(n)
3. P: Θ(n), Q: Θ(n log n), R: Θ(n^2)
4. P: Θ(1), Q: Θ(n), R: Θ(n log n)

Correct answer: P: Θ(1), Q: Θ(n), R: Θ(n)

Solution

For an unsorted doubly linked list with head and tail pointers, melding can be done by linking the tail of one list to the head of the other in constant time. For a min-heap and a binary search tree, the elements generally need to be restructured to preserve the heap/BST property, which takes linear time in the worst case.

Related GATE Technical questions

• A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
• An array \([82, 101, 90, 11, 111, 75, 33, 131, 44, 93]\) is heapified. Which one of the following options represents the first three elements in the heapified array?
• Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index in the underlying array of the maximum element stored in the heap. The number of possible values of \(k\) is
• Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
• The height of a binary tree is the maximum number of edges in any root-to-leaf path. The maximum number of nodes in a binary tree of height $h$ is:
• The maximum number of binary trees that can be formed with three unlabeled nodes is:

⚔️ Practice GATE Technical free + battle 1v1 →