Explanation: Heap sort is an implementation of selection sort using the input array as a heap representing a descending priority queue. Heap sort algorithm is divided into two phase. In first phase the max-heap is created and the second phase (selection phase) deletes the elements from the priority queue using siftdown operation.

Explanation: Heap sort is a comparison based sorting algorithm and has time complexity O(nlogn) in the average case. Heap sort is an in-place algorithm as it needs O(1) of auxiliary space. Heap sort uses heap and operations on heap can change the relative order of items with the same key values. Therefore, Heap sort is not a stable sort.

Explanation: The max-heap is also known as descending heap. Max-heap of size n is an almost complete binary tree of n nodes such that the element at each node is less than or equal to the element at its parent node.

Explanation: In Heap sort, the call to procedure build_Max-heap takes O(n) time and each of O(n) calls to the function max_Heapify takes O(logn) time. So the worst case complexity of Heap sort is O(nlogn).

Explanation: Quick sort is more efficient than Heap sort because experiments indicate that Heap sort requires twice as much time as Quick sort for randomly sorted input.

Explanation: Steps in heap sort are : (i) Build the max-heap, (ii) Swap the root element with the last element of the heap, (iii) Reduce the size of heap by 1 and heapify the root element, (iv) Repeat the steps form step number (v) until all the elements are sorted. Therefore the correct option is swap(arr[0], arr[i]).

Explanation: Smooth sort is a variation of Heap sort. Smooth sort has O(nlogn) worst case time complexity like Heap sort. But Smooth sort takes O(n) time to sort the nearly sorted input array.

Explanation: Introsort is a hybrid sorting algorithm that combines Quick sort and Heap sort to retain advantages of both. It has worst case speed of Heap sort and average case speed of Quick sort.