Heap Sort
1. Which of the following sorting algorithms, in its typical implementation, gives the best performance when applied to an array that is sorted or almost sorted (with at most 1 or 2 elements misplaced)?
2. Consider a binary min heap containing n elements, where every node has degree 2 (i.e., a full binary min heap tree). What is the probability of finding the largest element at the last level?
3. In a max-heap, the element with the greatest key is always in which node?
4. Heap can also be used as _______.
5. An array consists of n elements. We want to create a heap using these elements. The time complexity of building a heap will be in the order of ________.