Heap Sort

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