This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “D-ary Heap”.
1. How many comparisons will occur while performing a delete-min operation?
Explanation: Since the delete-min operation is more costly and the heap is shallow, d-1 comparisons can be used to find the minimum of d elements.
2. How many basic operations can be performed in a d-heap?
Explanation: Insert and delete-min operations are the two basic operations performed in a d-heap.
3. What is the run time efficiency of delete-min operation?
A) O(log N)
B) O(logd N)
C) O(d logd N)
Explanation: Mathematically, a delete-min algorithm using d-1 comparisons has a run time efficiency of O. (d logd N).
4. The following figure is an example for
5. Multiplication and division to find children and parents cannot be implemented in a d-heap.
Explanation: In a d-heap, multiplication and division can be used to locate children and parents, but d should be a power of two.
6. How many secondary operations are performed in a d-heap?
Explanation: Increasekey, decreasekey, buildheap, and delete are the other operations that can be performed on a d-heap.
7. On which data structure is a d-ary heap based?
C) linked list
D) priority queue
Explanation: A d-ary heap is a data structure that is built on a priority queue and is a generalisation of binary heaps.
8. d-heap is similar to that of a?
A) binary heap
B) fibonacci heap
C) leftist heap
Explanation: A d-heap is equivalent to a binary heap, with the exception that binary heaps have two children whereas d-heaps have d.
9. d-heap is shallower than a binary heap.
Explanation: A d-heap is much shallower than a binary heap in terms of insert and delete performance quality.
10. Which operation cannot be directly performed in a d-heap?
Explanation: In a d-heap, the find operation is not possible as it is in other heaps. The biggest flaw of d-heap is this.
11. Which operation is not efficiently performed in a d-heap?
Explanation: In contrast to the find operation, which cannot be done in a d-heap, combining two d-heaps is a difficult job.
12. What is the run time efficiency of an insertion algorithm in d-heap?
B) O(log N)
C) O(logd N)
Explanation: In a d-heap, the run time efficiency of an insertion algorithm is O(logd N), where d is the number of children.
The d-ary heap, also known as the d-heap, is a priority queue data structure that is a generalisation of the binary heap with d children instead of two. A binary heap is a two-heap, while a ternary heap is a three-heap. Donald B. Johnson invented d-ary heaps in 1975, according to Tarjan and Jensen et al. At the cost of slower delete minimum operations, this data structure allows decrease priority operations to be done more rapidly than binary heaps. For algorithms like Dijkstra’s algorithm, where decrease priority operations are more popular than delete min operations, this tradeoff results in faster running times.