With its time complexity of O(n log(n)) heapsort is optimal. It utilizes a special data structure called heap. This data structure is explained in the following.
Basics
Definition: Let T = (V, E) an almost complete binary tree with a vertex labelling a : V M that assigns to each vertex u a label a(u) from an ordered set (M, ).
A vertex u V has the heap property if it has no direct descendant with a greater label, i.e.
v V : (u, v) E a(u) a(v)
T is a heap if all vertices have the heap property, i.e.
(u, v) E : a(u) a(v)
We call T a semiheap if all vertices except possibly the root r have the heap property, i.e.
(u, v) E, ur : a(u) a(v)
Example:


Figure 1: Heap with n = 10 vertices  
Observe that each leaf automatically has the heap property regardless of its label, since it has no descendants. >>>>
Leave a Reply