Heapsort

1.A heap is a binary tree satisfying the followingconditions:

-This tree is completely balanced.

-If the height of this binary tree is h, then leaves can be at level h or level h-1.

-All leaves at level h are as far to the left as possible.

-The data associated with all descendants of a node are smaller than the datum associated with this node.



Implementation

1.using a linear array not a binary tree.

-The sons of A(h) are A(2h) and A(2h+1).

2.time complexity: O(n log n)