topic – RBR

Heap-Tree

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.

511

Data-Structures Heap-Tree GATE 2020

Question 1 Explanation:

The binary heap contains 1023 elements.
When it performs minimum comparisons it will take Ceil(n/2)
n=1023
= Ceil(1023/2)
= 512
So, the maximum element is also part of n/2. So, we have to subtract from the total elements
=512-1
=511

Question 2

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.

A	80
B	81
C	82
D	83

Data-Structures Heap-Tree Gate 2018

Question 2 Explanation:

--> We have 7 distinct integers {1,2,3,4,5,6,7} and sort it
--> After sorting, pick the minimum element and make it the root of the min heap.
--> So, there is only 1 way to make the root of the min heap.
--> Now we are left with 6 elements.
--> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80

Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .

Question 3

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________.

A	8
B	9
C	10
D	11

Data-Structures Heap-Tree GATE 2016 set-2

Question 3 Explanation:

This is not possible because it violates a property of complete binary tree.
We have total [0, 1023] elements. It means that

∴ 2⁰ + 2¹ + 2² + ⋯ + 2^k = 1024
Add if 1(2^(k+1)-1)/(2-1) [using formula for sum of k terms k+1 in G.P]
= 2^(k+1) - 1 = 1024 - 1 = 1023
∴ The level ‘9’ at the depth of 8.
Actually we have 1023 elements, we can achieve a complete binary min heap of depth 9, which would cover all 1023 elements, but the max depth of node 9 can be only be 8.

Question 4

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

A	Ω(logn)
B	Ω(n)
C	Ω(nlog n)
D	Ω(n²)

Data-Structures Heap-Tree GATE 2015 -(Set-2)

Question 4 Explanation:

Since left and right subtree is already a heap. So we can apply Heapify (node) which take log n time.

Question 5

Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is

A	4
B	5
C	2
D	3

Data-Structures Heap-Tree GATE 2015(Set-03)

Question 5 Explanation:

Let's first draw heap from the given array,

→ Swap 100 & 15

→ Swap 100 & 50

→ Swap 89 & 100

∴ Total 3 interchanges are needed.

Question 6

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

A	{25,12,16,13,10,8,14}
B	{25,14,13,16,10,8,12}
C	{25,14,16,13,10,8,12}
D	{25,14,12,13,10,8,16}

Data-Structures Heap-Tree 2009

Question 6 Explanation:

Option-A:

Violating a max heap property.
Option-B:

Violating a max heap property.
Option-C:

Question 7

Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on the correct answer to the previous question?

A	{14,13,12,10,8}
B	{14,12,13,8,10}
C	{14,13,8,12,10}
D	{14,13,12,8,10}

Data-Structures Heap-Tree 2009

Question 7 Explanation:

Actual Graph:

Step 1: Delete 25

Step 2:

Step 3: Delete 16

Step 4:

Step 5:

∴ Finary array elements: 14, 13, 12, 8, 10.

Question 8

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

A	θ(log n)
B	θ(n)
C	θ(nlog n)
D	θ(n²)

Data-Structures Heap-Tree Gate-2008

Question 8 Explanation:

Inserting an element into binary(either max or min) heap takes O(logn) for all cases, but in question they clearly mentioned that n elements and inserting one by one n elements, so it takes 2n time. So, O(n).
Note: We can also insert all the elements once, there will be no difference on time complexity.

Question 9

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

A	θ(log₂n)
B	θ(log₂log₂n)
C	θ(n)
D	θ(nlog₂n)

Data-Structures Heap-Tree Gate-2007

Question 9 Explanation:

Max heap is the complete binary tree that means each node has either zero children or two children except last level. So in worst case insertion of element is at last level. So, number of comparisons required at each level starting from root is equal to 1+2+4+8+16+---- this series is equal to "logn". All the elements are sorted, the binary search which will result in O(loglogn) number of comparisons.

Question 10

In a binary max heap containing n numbers, the smallest element can be found in time

A	O(n)
B	O(log n)
C	O(log log n)
D	O(1)

Data-Structures Heap-Tree Gate-2006

Question 10 Explanation:

We have to search all the elements in max heap. So, the worst case time complexity for Max Heap is O(n).

Question 11

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?

A	10, 7, 9, 8, 3, 1, 5, 2, 6, 4
B	10, 9, 8, 7, 6, 5, 4, 3, 2, 1
C	10, 9, 4, 5, 7, 6, 8, 2, 1, 3
D	10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Data-Structures Heap-Tree Gate-2006

Question 11 Explanation:

Question 12

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

A	1, 3, 5, 6, 8, 9
B	9, 6, 3, 1, 8, 5
C	9, 3, 6, 8, 5, 1
D	9, 5, 6, 8, 3, 1

Data-Structures Heap-Tree Gate-2006

Question 12 Explanation:

Question 13

Which of the following sequences of array elements forms a heap?

A	{23, 17, 14, 6, 13, 10, 1, 12, 7, 5}
B	{23, 17, 14, 6, 13, 10, 1, 5, 7, 12}
C	{23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
D	{23, 17, 14, 7, 13, 10, 1, 12, 5, 7}

Data-Structures Heap-Tree Gate 2006-IT

Question 13 Explanation:

In this every children and parent satisfies Max heap properties.

Question 14

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a MaxHeap. The resultant MaxHeap is

A
B
C
D

Data-Structures Heap-Tree Gate-2004

Question 14 Explanation:

32, 15, 20, 30, 12, 25, 16

Question 15

In a heap with n elements with the smallest element at the root, the 7^th smallest element can be found in time

A	Θ(n log n)
B	Θ(n)
C	Θ(log n)
D	Θ(1)

Data-Structures Heap-Tree Gate-2003

Question 15 Explanation:

The 7^th smallest elements can be present in any of 7 levels. Then total possible elements can be present is seven levels is
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7^th smallest element in Θ(1) time.

Question 16

A	0
B	1
C	2
D	3

Data-Structures Heap-Tree Gate-1996

Question 16 Explanation:

Lets draw first heap from given sequence,

Question 17

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i≤n), the index of the parent is

A
B
C
D

Data-Structures Heap-Tree Gate-2001

Question 17 Explanation:

Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1

There are 17 questions to complete.