Explore topic-wise InterviewSolutions in .

Right answer is (C) merging

Best explanation: The fundamental OPERATION of SKEW heaps is merging. Hence, it is similar to that of a LEFTIST HEAP.

Correct ANSWER is (b) O(log N)

Best explanation: Skew heaps support merging, INSERTION and deletion all effectively in O(log N) TIME PER OPERATION.

Correct ANSWER is (c) lack of stack SPACE

For explanation: In skew heaps, a RECURSIVE implementation could fail because of lack of stack space EVEN though performance is acceptable.

Correct option is (a) Skew heaps

The BEST I can EXPLAIN: It is an open problem to determine precisely the expected right path LENGTH of both LEFTIST and skew heaps and comparatively, the latter is difficult.

Right choice is (a) O(N)

To EXPLAIN: The worst-case analysis for the naïve MERGE is an INSERTION in a right heavy tree. So, insertion takes O(N).

The CORRECT answer is (B) 2

Best explanation: Two kinds of the merge are AVAILABLE in SKEW heaps- naïve merge and skew merge.

The correct choice is (b) false

Best explanation: In SKEW HEAPS, swaps are UNCONDITIONAL. It is done with the exception that the largest of all NODES does not have its CHILDREN swapped.

The correct choice is (a) MAX heap

Easiest EXPLANATION - Descending priority QUEUE arranges the ELEMENTS based on their priority or value and allows REMOVING the elements in descending order. So, it can be efficiently implemented using max heap.

Right option is (a) True

To explain: In MIN heap, the insertion and deletion operation takes O(LOGN) time. Therefore, a selection SORT with n INSERTIONS and n DELETIONS can be implemented using a min heap in O(nlogn) operations.

Right answer is (b) A[PARENT(i)] <= A[i]

Best EXPLANATION: The min heap is also known as ascending heap. Min heap of SIZE n is an almost complete binary tree of n nodes such that the element at each node is greater than or equal to the element at its parent node.

The correct option is (d) constant and logarithmic TIME respectively

The best I can explain: In the min heap, the root is the maximum element in the tree. So, LOCATING it takes constant time, but deleting it takes logarithmic time. Because after deleting it, the root is replaced with LAST element and then the PROCEDURE to maintain the min ORDERING is invoked.

Right answer is (a) O(n)

The best I can EXPLAIN: In MIN heap the SMALLEST is located at the root and the largest elements are located at the leaf nodes. So, all leaf nodes need to be checked to find the largest element. Thus, worst case TIME will be O (n).

Right option is (a) True

The best EXPLANATION: A tree, in which all levels are fully filled, except possibly the last LEVEL, is called as the COMPLETE binary tree. And min HEAP maintains shape property, so it is a complete binary tree. The shape property ensures that all levels in the min heap are fully filled, except the last one, and, if the last level is not filled completely, then fill the ELEMENTS from left to right.

Right option is (b) 5 will be at last level

Best explanation: In MAX heap the greatest element is at the ROOT and the smallest ELEMENTS are at the last level. As 5 is the smallest INPUT element, it will be at the last level.

Right CHOICE is (a) SPLAY tree and AVL tree

The best I can explain: Splay tree is a self -ADJUSTING VERSION of AVL tree. Similarly, skew heap is a self-adjusting version of leftist heap.

The correct choice is (d) O(log N)

For explanation: The AMORTIZED cost PER operation of a SKEW heap is O(log N) since the WORST case ANALYSIS of skew heap is O(N) and splay tree is O(M log N).

The correct answer is (a) O(N)

Easiest explanation - The worst CASE running TIME of all operations in a skew HEAP is MATHEMATICALLY found to be O(N).

Right CHOICE is (a) O(N)

BEST EXPLANATION: The mathematical calculation yields a result that, a leftist heap can be built in O(N) time by BUILDING a binary heap.

Correct ANSWER is (c) O(log N)

The explanation is: The time TAKEN to delete a minimum element in a LEFTIST HEAP is mathematically found to be O(log N).

Correct answer is (d) violation at the root

To explain: When two leftist HEAPS are merged, if the left subtree of the root has a null path length of 1 and the right subtree has a null path length of 2, leftist PROPERTY is violated at the root.

The correct answer is (c) RIGHT PATH

The EXPLANATION is: All the operations are PERFORMED on the right path because right paths are short. HOWEVER, insertion and merges cannot be performed on the right path.

Right option is (B) the tree is biased to GET DEEP down the left

The best explanation: The heap is named as leftist heap because it tends to have deep left paths. It FOLLOWS that the right path ought to be SHORT.

The correct answer is (C) 0

The explanation is: The length of the shortest path from a NODE to a node without TWO children is defined as 0.

Correct answer is (d) O(LOG N)

The best explanation: The efficiency of MERGE operations in leftist heap is mathematically found to be O( log N) which is the same in binary heaps.

The correct answer is (a) true

Easiest EXPLANATION - A LEFTIST heap has a STRUCTURAL property and an ordering property which is similar to that of a binary heap. Hence, leftist heap is also SAID to be binary heap.

The correct option is (b) merging

The EXPLANATION is: The fundamental OPERATIONS on leftist heaps is MERGE. Insertion operation is a merge of a one-node heap with a LARGER heap.

The correct ANSWER is (c) delete

Best EXPLANATION: Performing insert and merge operations on the right path COULD destroy the leftist HEAP property. It is extremely easy to restore that property.

Correct answer is (B) 2^r-1

The best explanation: A leftist tree with r NODES on the RIGHT path is proved to have at least 2^r-1 nodes. This theorem is proved by induction.

Correct choice is (d) -1

To EXPLAIN: In a LEFTIST heap tree, the null path length of a null NODE with no CHILDREN is defined as -1.

Correct choice is (c) 3

To EXPLAIN: A leftist HEAP supports TWO properties- structural property, ORDERING property and a heap order property.

The CORRECT answer is (a) true

Easiest explanation - USE of pointers for merging reduces the speed of other operations. This is the main drawback of all ADVANCED data structures.

The CORRECT option is (a) O(N)

BEST explanation: The run time EFFICIENCY of an insertion ALGORITHM in a pairing heap is mathematically found to be O(N).

Correct option is (a) fibonacci heap

The best I can explain: ALTHOUGH pairing heap is an efficient algorithm, it is worse than the Fibonacci heap. Also, pairing heap is FASTER than d-ary heap and BINARY heap.

The CORRECT answer is (b) O(log N)

Best explanation: The AMORTIZED time efficiency for performing DELETION of a minimum element is mathematically FOUND to be O(log N).

Correct CHOICE is (B) False

For explanation: The heap ordering PROPERTY requires that all the root ELEMENTS of the subtrees in the list are not SMALLER than the root element of the heap.

Correct ANSWER is (a) splay tree

Explanation: The pairing HEAPS insertion, deletion and search time complexity was initially INSPIRED by that of splay TREES.

The correct option is (d) pairing HEAP

BEST explanation: Pairing heap is the best choice for COMPLEX APPLICATIONS because it is SIMPLE and better than the others.

Correct ANSWER is (C) c-1

Best explanation: If there are c children of the root, then c-1 MERGES are required to reassemble the pairing heap.

Right choice is (a) merge

Best explanation: The basic operation performed in a PAIRING HEAP is merging. INSERTION is ALSO DONE by merging.

Correct option is (c) left most child

Easiest explanation - A NODE that is a LEFTMOST node contains a POINTER to its parent, otherwise, the node is a right SIBLING.

The CORRECT choice is (c) heap ordered TREE

Best explanation: A pairing heap is represented as a heap-ordered tree and the ANALYSIS of pairing heap is open.

The CORRECT OPTION is (a) SIMPLICITY

Explanation: The reason for the simplicity of a pairing heap is its simplicity as it is SIMPLER and outperform other heap STRUCTURES.

The CORRECT option is (a) Prim’s ALGORITHM

To explain: When working on the graph in the COMPUTER science field, the Prim’s Algorithm for spanning trees uses a minimum ternary heap as there are delete operation equal to a number of edges and DECREASE priority operation equal to the number of vertices associated with the graph.

The correct answer is (C) O (n)

The explanation is: Ternary Heap can be formed by TWO swapping operations. Therefore, the TIME complexity for creating a ternary heap using two swapping operation is FOUND to be O (n).

The correct choice is (a) True

The BEST EXPLANATION: Ternary heap is a type of DATA structure in the field of computer science. It is a PART of the Heap data structure family. Due to the SWAPPING process, they have better memory cache behavior.