Heaps And Heapsort

A heap is a specialized tree-based data structure that satisfies the heap property.If Y is the child node of X,then key(X) >= key(Y). Such a heap is called a max heap and the opposite one is called a min heap.

The operations commonly performed with a heap are:

1)delete-max or delete-min:removing the root node of a max or min-heap,respectively.
2)increase-key or decrease-key:updating a key within a max or min-heap,respectively.
3)merge:joining two heaps to form a valid new heap containing all the elements of both.

Heaps are used in the sorting algorithm called heapsort.

HEAPSORT:

Heap sort is one of the best methods being in-place and with no quadratic worst case scenarios.It is a comparision based sorting algorithm, ans is part of the selection sort family.The operations performed by heap sort algorithm are:

BUILD-MAX-HEAP:To build a max heap with the given [1,n] elements.
MAX-HEAPIFY:Which modifies a heap with [1,n-1] elements so that it satifies the properties of a heap.

The following are the basic questions on heaps:

1)What are the properties of a heap?
2)What is the height of an n-element heap?
3)Where in a max-heap might the smallest element reside, assuming that all the elements are distinct?
4)Is an array that is in sorted order a min-heap?
5)What are the minimum and maximum numbers of elements in a heap of height h?
6)How many nodes are present in an n-element heap of height h?
7)What is the running time complexity of a heapsort?
8)What is the worst-case running time of a heapsort?
9)What is the running time of heapsort on an array A of length n that is alreay sorted in increasing order? What about the same in decreasing order?
10)What is the best case running time of heapsort when all the elements are distinct?
11)Name some applications of heaps