Data Structure Questions and Answers – Weak Heap

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Weak Heap”.

1. What is the complexity of given function of insertion.

	insert(int n)
		if(buffer_size()< maxi_biffer_size())

A) O(logn)
B) amortized O(1)
C) O(n)
D) O (n*logn)

Explanation: When a buffer is completed, the contents of the buffer are transferred to the heap. As a consequence, the complexity is reduced by a factor of O. (1).

2. Does there exist a heap with seven distinct elements so that the Inorder traversal gives the element in sorted order.
A) Yes
B) No

Explanation: No,The elements will not be returned in sorted order using the inorder traversal. Since heap is implemented as either a min-heap or a max-heap, the root would have the highest or lowest value compared to the nodes’ remaining values. As a result, this traversal will not result in a sorted list.

3. The leaf node for a heap of height h will be at which position.
A) h
B) h-1
C) h or h-1
D) h-2

Explanation: Since a complete binary tree is also a heap, the leaf nodes of a binary tree must be at height h or h-1.

4. Choose the correct properties of weak-heap.
A) Every node has value greater than the value of child node
B) Every right child of node has greater value than parent node
C) Every left child of node has greater value than parent node
D) Every left and right child of node has same value as parent node

Explanation: The property of a poor heap is this.

5. Left child of parent node has value lesser than the parent node.
A) True
B) False

Explanation: There is no child left in the weak heap.

6. What is the other name of weak heap?
A) Min-heap
B) Max-heap
C) Relaxed -heap
D) Leonardo heap

Explanation: Weak heap is also known as relaxed heap.

7. What is the worst case time in searching minimum value in weak -heap?
A) O(log n)
B) O(n)
C) O(n logn)
D) O(1)

Explanation: The weak heap is an array-based form that allows you to find a minimum in O. (1).

8. The total comparisons in finding both smallest and largest elements are
A) 2*n +2
B) n + ((n+1)/2) -2
C) n+logn
D) n2

Explanation: The total number of comparisons in the search for the smallest and largest elements is n + ((n+1)/2) – 2.

The weak heap is a data structure for priority queues that combines binary and binomial heap functionality. It has the efficiency guarantees of binomial heaps and can be stored in an array as an implicit binary tree, similar to a binary heap. Weak-heapsort, a sorting algorithm based on weak heaps, uses a number of comparisons that is close to the theoretical lower bound on the number of comparisons needed to sort a list, making it especially useful when comparison is time-consuming, such as when comparing strings using the full Unicode collation algorithm.

Leave a Reply

Your email address will not be published.