A Heapsort is based on a heap data structure. A heap is a
complete binary tree. This means that every successive level
of the tree must fill up from left to right. Further, an entire level
must be full before any nodes at that level can have children nodes. In a heap, the parent nodes always have a
greater (or lower) key value than their children nodes. A heap in
which the parents are always greater than their children is called a
max-heap whereas the opposite is called a min-heap.