Q.1 What type of data structure is primarily used in Heap Sort?
Queue
Stack
Heap
Graph
Explanation - Heap sort uses a binary heap data structure (commonly max-heap or min-heap) to perform sorting efficiently.
Correct answer is: Heap
Q.2 What is the time complexity of Heap Sort in the worst case?
O(n)
O(n log n)
O(log n)
O(n^2)
Explanation - In the worst case, Heap Sort performs O(n log n) operations due to repeated heapify calls.
Correct answer is: O(n log n)
Q.3 Which heap is generally used for Heap Sort?
Min Heap
Max Heap
Fibonacci Heap
Binomial Heap
Explanation - Heap Sort typically uses a max-heap to extract the largest element and place it at the end of the array.
Correct answer is: Max Heap
Q.4 Heap Sort is based on which technique?
Divide and Conquer
Greedy
Dynamic Programming
Transform and Conquer
Explanation - Heap Sort is a transform-and-conquer algorithm where input is first transformed into a heap structure.
Correct answer is: Transform and Conquer
Q.5 What is the auxiliary space complexity of Heap Sort?
O(n)
O(1)
O(log n)
O(n log n)
Explanation - Heap Sort sorts the array in place using constant extra space, hence O(1) auxiliary space.
Correct answer is: O(1)
Q.6 Which of the following is TRUE about Heap Sort?
It is stable
It is not stable
It always requires extra array
It is based on recursion only
Explanation - Heap Sort is not stable since the relative order of equal elements may not be preserved.
Correct answer is: It is not stable
Q.7 The process of rearranging elements to satisfy heap properties is called?
Insertion
Deletion
Heapify
Balancing
Explanation - Heapify is the process of rearranging elements in a binary tree so that it satisfies heap property.
Correct answer is: Heapify
Q.8 In Heap Sort, the root of the max-heap contains?
Smallest element
Largest element
Median element
Random element
Explanation - In a max-heap, the largest element is always at the root node.
Correct answer is: Largest element
Q.9 Heap Sort can be used for?
Internal sorting
External sorting
Only linked list sorting
Only stack sorting
Explanation - Heap Sort is an internal sorting algorithm since it works completely within main memory.
Correct answer is: Internal sorting
Q.10 Which traversal method of heap is used to implement Heap Sort?
Inorder
Preorder
Level order
Postorder
Explanation - Heap is a complete binary tree represented in arrays using level order traversal.
Correct answer is: Level order
Q.11 The height of a heap with n elements is?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - The height of a heap with n elements is O(log n), as it is a complete binary tree.
Correct answer is: O(log n)
Q.12 Heap Sort is considered better than Quick Sort in?
Average case
Worst case
Best case
All cases
Explanation - Heap Sort guarantees O(n log n) in the worst case, unlike Quick Sort which can degrade to O(n^2).
Correct answer is: Worst case
Q.13 Which operation is repeatedly applied in Heap Sort after extracting the root?
Reheapify
Restructure
Rebalance
Reorder
Explanation - After removing the root element, the heap property is restored using reheapify.
Correct answer is: Reheapify
Q.14 Heap Sort is best suited for?
Small datasets
Linked lists
Large datasets in arrays
Sparse matrices
Explanation - Heap Sort works best for large arrays because of its O(n log n) complexity and in-place sorting nature.
Correct answer is: Large datasets in arrays
Q.15 Which of the following is TRUE about Heap Sort?
Recursive calls are mandatory
It can be implemented iteratively
It requires extra memory always
It cannot be implemented in-place
Explanation - Heap Sort can be implemented iteratively without recursion for heapify operations.
Correct answer is: It can be implemented iteratively
Q.16 What is the best case time complexity of Heap Sort?
O(n)
O(log n)
O(n log n)
O(n^2)
Explanation - Unlike other algorithms, even in the best case, Heap Sort requires O(n log n).
Correct answer is: O(n log n)
Q.17 Heap Sort is an example of?
Comparison-based sorting
Non-comparison sorting
Counting sort
Bucket sort
Explanation - Heap Sort compares elements to establish heap properties and sort the array.
Correct answer is: Comparison-based sorting
Q.18 Which of the following applications use Heap Sort?
CPU scheduling
Priority queues
Dijkstra’s algorithm
All of the above
Explanation - Heap structure (basis of Heap Sort) is widely used in priority queues, CPU scheduling, and shortest path algorithms.
Correct answer is: All of the above
Q.19 Heap Sort works efficiently when data is stored in?
Linked lists
Arrays
Trees
Graphs
Explanation - Heap Sort is efficient with arrays as heaps can be easily represented using array indexing.
Correct answer is: Arrays
Q.20 Which of the following is FALSE about Heap Sort?
It is in-place
It is stable
It is comparison-based
It is O(n log n)
Explanation - Heap Sort is not stable as it may change the relative order of equal elements.
Correct answer is: It is stable
Q.21 What is the first step in Heap Sort?
Extract minimum
Build a heap
Insert element
Sort the half array
Explanation - The first step is to build a heap from the unsorted array before repeatedly extracting elements.
Correct answer is: Build a heap
Q.22 The array representation of a binary heap is based on?
Breadth First Search
Depth First Search
Level order traversal
Inorder traversal
Explanation - Binary heap is represented using level order traversal in arrays.
Correct answer is: Level order traversal
Q.23 Heap Sort can be applied to?
Only integers
Only strings
Any comparable data type
Only floating-point numbers
Explanation - Heap Sort works on any data type that supports comparison operations.
Correct answer is: Any comparable data type
Q.24 Which is better in practice for average cases: Heap Sort or Quick Sort?
Heap Sort
Quick Sort
Both equal
Neither
Explanation - Quick Sort generally outperforms Heap Sort in average cases due to better cache performance.
Correct answer is: Quick Sort
Q.25 What is the recurrence relation for Heap Sort?
T(n) = 2T(n/2) + O(1)
T(n) = T(n-1) + O(log n)
T(n) = T(n-1) + O(n)
T(n) = T(n/2) + O(n)
Explanation - Heap Sort extracts one element (O(log n)) and recursively heapifies the remaining n-1 elements.
Correct answer is: T(n) = T(n-1) + O(log n)