Heaps and Priority Queues Questions and Answers

Q: An operator delete(\(i\)) for a binary heap data structure is to be designed to delete the item in the \(i\)-th node. Assume that the heap is implemented in an array and \(i\) refers to the \(i\)-th index of the array. If the heap tree has depth \(d\) (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

The time is \(O(d)\) but not \(O(1)\).To delete the element at index \(i\), replace it with the last element of the heap and shrink the heap by one. The moved element may now violate the heap property in one direction only: if it is larger than its parent (in a max-heap) it must sift up; if it is smaller than a child it must sift down. Either way it moves along a single root-to-leaf path, at most \(d\) levels, so re-fixing takes \(O(d)\) time.It is not \(O(1)\) in general, since the element may have to travel the whole height. \(O(2^{d})\) and \(O(d\,2^{d})\) are the order of the number of nodes, which would mean rebuilding much of the heap instead of sifting one element.

Q: 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?

The first three elements are 131, 111, 90.Heapify here builds a max-heap bottom-up, sifting down from the last internal node (index 4, value 111) to the root:111 already exceeds its child 93.11 swaps with its larger child 131.90 stays above 75 and 33.101 swaps with 131, then stays above 11 and 44.82 swaps with 131, then with 111, then with 93.The result is [131, 111, 90, 101, 93, 75, 33, 11, 44, 82]. The root must be the maximum, 131, which rules out the options starting with 82. Option C puts 11 at index 1, above larger elements such as 101, which a max-heap forbids.

Q: 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

The number of possible positions is 53.In a min-heap every internal node is smaller than its children, so the maximum element cannot be an internal node: it must be a leaf. With 105 elements stored in an array indexed from 1, the internal nodes are indices 1 to \(\lfloor 105/2 \rfloor = 52\) and the leaves are 53 to 105:\[ 105 - 52 = 53\ \text{leaves} \]Any leaf can hold the maximum, since a leaf has no children to compare against. 52 counts the internal nodes instead, and 1 would assume the maximum has a fixed position, which is true only of the minimum (at the root).

Q: Which one of the following sequences when stored in an array at locations \(A[1], \ldots, A[10]\) forms a max-heap?

The max-heap is 23, 17, 14, 7, 13, 10, 1, 5, 6, 12.In an array heap the children of \(A[i]\) are \(A[2i]\) and \(A[2i+1]\), and every parent must be at least as large as its children. For this sequence:A[1] = 23: children 17 and 14A[2] = 17: children 7 and 13A[3] = 14: children 10 and 1A[4] = 7: children 5 and 6A[5] = 13: child 12Every check passes. The others each break the rule once: in the first sequence A[3] = 10 has the child A[6] = 14; in the third A[5] = 13 has the child A[10] = 15; and in the fourth A[4] = 1 has the children 12 and 7.

An operator delete(\(i\)) for a binary heap data structure is to be designed to delete the item in the \(i\)-th node. Assume that the heap is implemented in an array and \(i\) refers to the \(i\)-th index of the array. If the heap tree has depth \(d\) (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

A.\(O(1)\)
B.\(O(d)\) but not \(O(1)\)
C.\(O(2^{d})\) but not \(O(d)\)
D.\(O(d\,2^{d})\) but not \(O(2^{d})\)

Exam Year(s)

GATE CS - 2016,

Answer: B

The time is \(O(d)\) but not \(O(1)\).

To delete the element at index \(i\), replace it with the last element of the heap and shrink the heap by one. The moved element may now violate the heap property in one direction only: if it is larger than its parent (in a max-heap) it must sift up; if it is smaller than a child it must sift down. Either way it moves along a single root-to-leaf path, at most \(d\) levels, so re-fixing takes \(O(d)\) time.

It is not \(O(1)\) in general, since the element may have to travel the whole height. \(O(2^{d})\) and \(O(d\,2^{d})\) are the order of the number of nodes, which would mean rebuilding much of the heap instead of sifting one element.

Discuss in Forum

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?

A.82, 90, 101
B.82, 11, 93
C.131, 11, 93
D.131, 111, 90

Exam Year(s)

GATE CS - 2024,

Answer: D

The first three elements are 131, 111, 90.

Heapify here builds a max-heap bottom-up, sifting down from the last internal node (index 4, value 111) to the root:

111 already exceeds its child 93.
11 swaps with its larger child 131.
90 stays above 75 and 33.
101 swaps with 131, then stays above 11 and 44.
82 swaps with 131, then with 111, then with 93.

The result is [131, 111, 90, 101, 93, 75, 33, 11, 44, 82]. The root must be the maximum, 131, which rules out the options starting with 82. Option C puts 11 at index 1, above larger elements such as 101, which a max-heap forbids.

Discuss in Forum

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

A.53
B.52
C.27
D.1

Exam Year(s)

GATE CS - 2024,

Answer: A

The number of possible positions is 53.

In a min-heap every internal node is smaller than its children, so the maximum element cannot be an internal node: it must be a leaf. With 105 elements stored in an array indexed from 1, the internal nodes are indices 1 to \(\lfloor 105/2 \rfloor = 52\) and the leaves are 53 to 105:

\[ 105 - 52 = 53\ \text{leaves} \]

Any leaf can hold the maximum, since a leaf has no children to compare against. 52 counts the internal nodes instead, and 1 would assume the maximum has a fixed position, which is true only of the minimum (at the root).

Discuss in Forum

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?

A.P: \(\Theta(1)\), Q: \(\Theta(n)\), R: \(\Theta(n)\)
B.P: \(\Theta(1)\), Q: \(\Theta(n\log n)\), R: \(\Theta(n)\)
C.P: \(\Theta(n)\), Q: \(\Theta(n\log n)\), R: \(\Theta(n^{2})\)
D.P: \(\Theta(1)\), Q: \(\Theta(n)\), R: \(\Theta(n\log n)\)

Exam Year(s)

GATE CS - 2025,

Answer: A

The meld complexities are P: \(\Theta(1)\), Q: \(\Theta(n)\), R: \(\Theta(n)\).

P, a doubly linked list with head and tail pointers: link the tail of the first list to the head of the second and update one tail pointer. A constant number of pointer changes: Θ(1).
Q, an array min-heap: copy both arrays into one of size 2n and run the bottom-up build-heap, which is linear: Θ(n). Inserting the elements one at a time would cost Θ(n log n), so that is not the best bound.
R, a binary search tree: an inorder traversal of each tree gives two sorted lists in Θ(n), merging them takes Θ(n), and a balanced BST can be built from a sorted list in Θ(n).

The other options take the slower insertion-based approaches for Q or R, or treat the list meld as linear.

Discuss in Forum

Which one of the following sequences when stored in an array at locations \(A[1], \ldots, A[10]\) forms a max-heap?

A.23, 17, 10, 6, 13, 14, 1, 5, 7, 12
B.23, 17, 14, 7, 13, 10, 1, 5, 6, 12
C.23, 17, 14, 6, 13, 10, 1, 5, 7, 15
D.23, 14, 17, 1, 10, 13, 16, 12, 7, 5

Exam Year(s)

GATE CS - 2023,

Answer: B

The max-heap is 23, 17, 14, 7, 13, 10, 1, 5, 6, 12.

In an array heap the children of \(A[i]\) are \(A[2i]\) and \(A[2i+1]\), and every parent must be at least as large as its children. For this sequence:

A[1] = 23: children 17 and 14
A[2] = 17: children 7 and 13
A[3] = 14: children 10 and 1
A[4] = 7: children 5 and 6
A[5] = 13: child 12

Every check passes. The others each break the rule once: in the first sequence A[3] = 10 has the child A[6] = 14; in the third A[5] = 13 has the child A[10] = 15; and in the fourth A[4] = 1 has the children 12 and 7.

Discuss in Forum

Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.

When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?

A.Both Extract-Max(A) and Insert(A,key) run in \(O(1)\).
B.Both Extract-Max(A) and Insert(A,key) run in \(O(\log(n))\).
C.Extract-Max(A) runs in \(O(1)\) whereas Insert(A,key) runs in \(O(n)\).
D.Extract-Max(A) runs in \(O(1)\) whereas Insert(A,key) runs in \(O(\log(n))\).

Exam Year(s)

GATE CS - 2023,

Answer: B

Both Extract-Max(A) and Insert(A,key) run in \(O(\log(n))\).

Extract-Max reads the maximum at the root in constant time, but it must also delete it: the last element is moved to the root and sifted down, swapping with the larger child until the heap property holds again. That can take one swap per level, and a heap of n elements has about \(\log_{2} n\) levels.

Insert places the new key in the next free leaf and sifts it up towards the root, again at most one swap per level, \(O(\log(n))\).

The options with Extract-Max in \(O(1)\) confuse finding the maximum with extracting it while keeping a valid heap. Insert is never \(O(n)\) in a binary heap, and neither operation is \(O(1)\) in the worst case.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Heaps and Priority Queues Questions and Answers || Heaps and Priority Queues MCQ Questions and Answers || Heaps and Priority Queues GK Questions and Answers || Heaps and Priority Queues GK MCQ Questions || Heaps and Priority Queues Multiple Choice Questions and Answers || Heaps and Priority Queues GK || GK on Heaps and Priority Queues || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Heaps and Priority Queues Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications