Heap Sort Interview Question Part 1

1. What is the average case complexity for heap sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c


2.What is the best case complexity for heap sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c


3.The condition applicable for max-heap is
a.A[Parent(i)]>=A[i]
b. A[Parent(i)]<=A[i]
c. A[Parent(i+1)]>A[i]
d. A[Parent(i+1)]Ans:a


4.The condition applicable for min-heap is
a.A[Parent(i)]>=A[i]
b. A[Parent(i)]<=A[i]
c. A[Parent(i+1)]>A[i]
d. A[Parent(i+1)] Ans:b


5.The number of operations required for heap sort regardless of the order of input
a.O(1)
b.O(logn)
c.O(nlogn)
d.O(n*n)
Ans:c

6.In which cases are the time complexities same in heap sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. Worst, average and Best
Ans:d

7.The heap sort property is __________.
a. A[Parent(I)] >=A[I]
b. A[Parent(I)] <=A[I]
c. A[Parent(I)]!=A[I]
d. None of the above
Ans. a


8.If a max heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value? (most appropriate answer)
a. data[0]
b. data[n-1]
c. data[n]
d. data[2*n + 1]
e. data[2*n + 2]
Ans. a


9.What is the worst-case time for heapsort to sort an array of n elements?
a. O(log n)
b. O(n)
c. O(n log n)
d. O(n²)
Ans. c

10.The frequency count for heapify process is(all logarithms are to the base 2)
a.log n
b.n log n
c.n*n
d.none
Ans:a

11. The frequency count for heap sort process is(all logarithms are to the base 2)
a.log n
b.n log n
c.n*n
d.none
Ans:b


12.The process of converting an array into a heap by executing heapify progressively closer to the root is called _________
Ans:build-heap
13.For an array of n nodes, build heap takes _______ time
A.O(logn)
b.O(n)
c.O(nlogn)
d.none
Ans:b
14. The Time Complexity of the Huffman code generation algorithm, when the forest is represented as a minHeap is:
(i) O(n² )
(ii) O(log n)
(iii) O(n log n)
(iv) O(n)
Answer: O(n log n) where the forest is stored as a minHeap. Each time the minimum element is deleted from the heap it costs log n. Since there are 2 deletions and one insertion during each iteration until the forest is empty,it costs n log n to build the tree.

15. The Time Complexity to list all the elements in a Heap is
(i) O(log n)
(ii) O(n log n)
(iii) O(1)
(iv) O(n)
Answer: Perform any order traversal of the tree - cost is O(n)

16. Draw the min-max heap after insertion of the following sequence of numbers 6, 3, 2, 5, 1, 1, 3.
Answer:
Order of nodes is:
level 1: 1
Level 2: 6 3
Level 3: 5 2 1 3