81. The number of elements that can be sorted in Q(log n) time using heap sort is
    

1. 1. Θ(1)
      

   
   
   

   2. Θ( √log n)
      

   
   
   

   3. Θ		log n
      		log log n

      
      

   
   
   

   4. Θ (log n)

   
   
   

---

1. View Hint View Answer Discuss in Forum

   The number of elements that can be sorted in Θ (log n) time using heap
   

   sort is Θ		log n
   		log logn

   
   Consider the number of elements is "k", which can be sorted in θ (k log k) time. Analyzing the options in decreasing order of complexity since we need a tight bound i.e., θ.
   

   i.e., θ (log n) , Θ		log n		, Θ(√log n) , Θ(1)
   		log logn

   
   So if k ∈ Θ (log n) time required for heap sort is O (k log k) i.e.,
   θ (log n × log log n), But this is not in Θ (log n)
   

   If k ∈ Θ		log n		time required for Heap Sort
   		log logn

   
   

   Θ		log n	× log		log n
   		log logn			log logn

   
   
   So, this is in Θ (log n)
   

   Hence , answer is (c) Θ		log n
   		log logn

   
   

   Correct Option: C

   The number of elements that can be sorted in Θ (log n) time using heap
   

   sort is Θ		log n
   		log logn

   
   Consider the number of elements is "k", which can be sorted in θ (k log k) time. Analyzing the options in decreasing order of complexity since we need a tight bound i.e., θ.
   

   i.e., θ (log n) , Θ		log n		, Θ(√log n) , Θ(1)
   		log logn

   
   So if k ∈ Θ (log n) time required for heap sort is O (k log k) i.e.,
   θ (log n × log log n), But this is not in Θ (log n)
   

   If k ∈ Θ		log n		time required for Heap Sort
   		log logn

   
   

   Θ		log n	× log		log n
   		log logn			log logn

   
   
   So, this is in Θ (log n)
   

   Hence , answer is (c) Θ		log n
   		log logn

   
   

---

82. A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is :
    

1. 1. 10, 8, 7, 3, 2, 1, 5
      

   
   
   

   2. 10, 8, 7, 2, 3, 1, 5
      

   
   
   

   3. 10, 8, 7, 1, 2, 3, 5
      

   
   
   

   4. 10, 8, 7, 5, 3, 2, 1

   
   
   

---

1. View Hint View Answer Discuss in Forum

   
   After insertion of elements, level - order tansvasal is: 10, 8, 7, 3, 2, 1, 5
   

   Correct Option: A

   
   After insertion of elements, level - order tansvasal is: 10, 8, 7, 3, 2, 1, 5
   

---

---

83. 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
    

1. 1. 4
      

   
   
   

   2. 5
      

   
   
   

   3. 2
      

   
   
   

   4. 3

   
   
   

---

1. View Hint View Answer Discuss in Forum

   
   1 st swap is : 100 and 15
   2 nd swap is : 100 and 50
   3 rd swap is : 100 and 89

   Correct Option: D

   
   1 st swap is : 100 and 15
   2 nd swap is : 100 and 50
   3 rd swap is : 100 and 89

---

84. Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.
    
    Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
    

1. 1. 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
      

   
   
   

   2. 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
      

   
   
   

   3. 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
      

   
   
   

   4. 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

   
   
   

---

1. View Hint View Answer Discuss in Forum

   
   
   
   
   

   Correct Option: B

   
   
   
   
   

---

---

85. 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 _______.

1. 1. 8

   
   
   

   2. 4

   
   
   

   3. 44

   
   
   

   4. 24

   
   
   

---

1. View Hint View Answer Discuss in Forum

   8
   Within ‘n’ levels of min heap, nth smallest element will be present.
   

   Correct Option: A

   8
   Within ‘n’ levels of min heap, nth smallest element will be present.
   

---