# Heapsort – Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Heapsort

1. In heap sort, after deleting the last minimum element, the array will contain elements in?
A) increasing sorting order
B) decreasing sorting order
C) tree inorder
D) tree preorder

Explanation: By logic, the heap will contain elements in decreasing sorting order after deleting the minimum element. This can be changed by changing the ordering property.

2. What is the typical running time of a heap sort algorithm?
A) O(N)
B) O(N log N)
C) O(log N)
D) O(N2)

Explanation: A heap sort algorithm’s cumulative running time is determined mathematically to be O. (N log N).

3. How many arrays are required to perform deletion operation in a heap?
A) 1
B) 2
C) 3
D) 4

Explanation: We need two arrays to perform a deletion operation in a heap, which takes up more memory and increases the running time.

4. What is the time taken to perform a delete min operation?
A) O(N)
B) O(N log N)
C) O(log N)
D) O(N2)

Explanation: The time it takes to delete a minimum element is found to be O in mathematics ( log N).

5. Heap sort is an extremely stable algorithm.
A) true
B) false

Explanation: Heap sort is a very robust algorithm since it uses fewer comparisons than other sorting algorithms.

6. What is the average number of comparisons used in a heap sort algorithm?
A) N log N-O(N)
B) O(N log N)-O(N)
C) O(N log N)-1
D) 2N log N + O(N)

Explanation: Mathematically, the average number of comparisons in a heapsort algorithm is 2N log N + O. (N).

7. What is the time taken to copy elements to and from two arrays created for deletion?
A) O(N)
B) O(N log N)
C) O(log N)
D) O(N2)

Explanation: The time it takes to copy elements between the main array and the extra array is discovered to be O. (N).

8. What is the average number of comparisons used to heap sort a random permutation of N distinct items?
A) 2N log N-O(N)
B) 2N log N-O(N log N)
C) 2N log N-O(N log log N)
D) 2N log N-O(log N)

Explanation: The average number of comparisons used to heap sort a random permutation of N distinct items is found to be 2N log N-O, according to a theorem (N log log N).

9. On which algorithm is heap sort based on?
A) Fibonacci heap
B) Binary tree
C) Priority queue
D) FIFO

Explanation: Heap sort uses a priority queue algorithm to have the fastest sorting time.

10. In what time can a binary heap be built?
A) O(N)
B) O(N log N)
C) O(log N)
D) O(N2)

Explanation: The fundamental strategy is to construct a binary heap of N elements in O(N) time.

11. Heap sort is faster than Shell sort.
A) true
B) false

Explanation: Since Shell sort uses Sedgewick’s increment series, heap sort is slower than Shell sort.

12. Consider the following heap after buildheap phase. What will be its corresponding array?

A) 26,53,41,97,58,59,31
B) 26,31,41,53,58,59,97
C) 26,41,53,97,31,58,59
D) 97,53,59,26,41,58,31

Explanation: Constructing a max heap using the elements 97,53,59,26,41,58,31 will cause the heap to look like that.

13. In what position does the array for heap sort contains data?
A) 0
B) 1
C) -1
D) anywhere in the array

Explanation: The array for heap sort starts at position 0, while the array for a binary heap starts at position 1. It’s because of this that it’s so complicated.

14. In average case Heap sort is as efficient as the Quick sort.
A) True
B) False

Explanation: Quick sort is more effective than Heap sort because tests show that for randomly sorted input, Heap sort takes twice as long as Quick sort.

15. Choose the correct option to fill? X so that the code given below implements the Heap sort.

```#include <stdio.h>
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
X;
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
printf(“%d”,arr[i]);
printf(“\n”);
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
printf(“Sorted array is \n");
printArray(arr, n);
}```

A) swap(arr[0], arr[n])
B) swap(arr[i], arr[n])
C) swap(arr[0], arr[i])
D) swap(arr[i], arr[2*i])

Explanation: The steps in heap sort are as follows: I Create the max-heap, (ii) Swap the root element with the last element of the heap, (iii) Reduce the size of the heap by 1 and heapify the root element, (iv) Repeat the steps from step number (v) until all of the elements are sorted. As a result, swap is the best alternative (arr[0], arr[i]).

16. Which one of the following is a variation of Heap sort?
A) Comb sort
B) Smooth sort
C) Binary tree sort
D) Shell sort

Explanation: Heap sort is a variant of Smooth sort. Smooth sort, like Heap sort, has a worst-case time complexity of O(nlogn). However, sorting the nearly sorted input array with Smooth sort takes O(n) time.

17. Introsort algorithm is combination of _____________
A) Quick sort and Heap sort
B) Quick sort and Shell sort
C) Heap sort and Merge sort
D) Heap sort and insertion sort

Explanation: Introsort is a hybrid sorting algorithm that combines the advantages of Fast sort and Heap sort. It has Heap sort’s worst case pace and Fast sort’s average case speed.

18. How many elements can be sorted in O(logn) time using Heap sort?
A) O(1)
B) O(n/2)
C) O(logn/log(logn))
D) O(logn)

Explanation: The time complexity of Heap sort is O(klogk) for k input elements,
for k = logn/log(logn),
O(klogk) = O(logn/log(logn) * log(logn/log(logn)))
∴ O(klogk) = O(logn/log(logn) * (log(logn) – log(log(logn))))
= O(logn)
Hence the correct option is O(logn/log(logn)).

19. Heap sort is an implementation of ____________ using a descending priority queue.
A) insertion sort
B) selection sort
C) bubble sort
D) merge sort

Explanation: Heap sort is a variation of selection sort that uses the input array to represent a descending priority queue as a heap. There are two phases to the heap sort algorithm. The max-heap is generated in the first step, and the elements from the priority queue are deleted in the second phase (selection phase) using the siftdown operation.

20. Which one of the following is false?
A) Heap sort is an in-place algorithm
B) Heap sort has O(nlogn) average case time complexity
C) Heap sort is stable sort
D) Heap sort is a comparison-based sorting algorithm

Explanation: Heap sort is a comparison-based sorting algorithm with an average time complexity of O(nlogn). Since it needs O(1) of auxiliary space, heap sort is an in-place algorithm. Heap sort is based on heap, and heap operations will alter the relative order of items with the same key values. As a result, heap sort isn’t a reliable sort.

21. The essential part of Heap sort is construction of max-heap. Consider the tree shown below, the node 24 violates the max-heap property. Once heapify procedure is applied to it, which position will it be in?

A) 4
B) 5
C) 8
D) 9

Explanation: Each node’s max-heap element is smaller or equal to the element at its parent node. When you use the heapify method on item 2, it will end up in position 9, as shown below.

22. The descending heap property is ___________
A) A[Parent(i)] = A[i]
B) A[Parent(i)] <= A[i]
C) A[Parent(i)] >= A[i]
D) A[Parent(i)] > 2 * A[i]

Explanation: The descending heap is another name for the max-heap. A max-heap of size n is an almost complete binary tree with n nodes in which each node’s element is less than or equal to its parent node’s element.

23. What is its wort case time complexity of Heap sort?
A) O(nlogn)
B) O(n2logn)
C) O(n2)
D) O(n3)

Explanation: The procedure build Max-heap takes O(n) time to call, and each of the O(n) calls to the function max Heapify takes O(logn) time. As a result, Heap sort’s worst-case complexity is O. (nlogn).

Heapsort is a comparison-based sorting algorithm used in computer science. Heapsort is similar to selection sort in that it divides its input into a sorted and an unsorted region, then iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time scanning the unsorted region in linear time; instead, heap sort keeps the unsorted region in a heap data structure to find the largest element in each stage more quickly.