HEAPSORT
The running time of heapsort is O(N*lgN) i.e. it
achieves the lower bound for computational based sorting.
HEAP
The heap data structure is an array object which can be easily visualized as a complete binary tree.There is a one to one correspondence between elements of the array and nodes of the tree.The tree is completely filled on all levels except possibly the lowest,which is filled from the left upto a point.All nodes of heap also satisfy the relation that the key value at each node is at least as large as the value at its children.
Step I: The user inputs the size of the heap(within a specified limit).The program generates a corresponding binary tree with
nodes having randomly generated key Values.
Step II: Build Heap Operation:Let n be the number
of nodes in the tree and i be the key of a tree.For this,the program uses
operation Heapify.when Heapify is called both the left and right subtree
of the i are Heaps.The function of Heapify is to let i settle down to a
position(by swapping itself with the larger of its children,whenever the
heap property is not satisfied)till the heap property is satisfied in the
tree which was rooted at (i).This operation calls
Step III: Remove maximum element:The program removes the largest element of the heap(the root) by swapping it with the last
element.
Step IV: The program executes Heapify(new root) so
that the resulting tree satisfies the heap property.
Step V: Goto step III till heap is empty
