Heaps and Heapsort

Heaps and Heapsort

1. Heap

   • A heap can be defined as a binary tree with keys assigned to its nodes, one key per node, provided the following two conditions are met
   • 1. The shape property—the binary tree is essentially complete
   • 2. The parental dominance or heap property

2. Important properties of heaps

   • There exists exactly one essentially complete binary tree with n nodes. Its height is equal to log2 n
   • The root of a heap always contains its largest element.
   • A node of a heap considered with all its descendants is also a heap.
   • A heap can be implemented as an array by recording its elements in the topdown, left-to-right fashion
     • the parental node keys will be in the first n/2 positions of the array, while the leaf keys will occupy the last n/2 positions;
     • the children of a key in the array’s parental position i (1 ≤ i ≤ n/2) will be in positions 2i and 2i + 1, and, correspondingly, the parent of a key in position i (2 ≤ i ≤ n) will be in position i/2.

3. //Constructs a heap from elements of a given array // by the bottom-up algorithm //Input: An array H[1..n] of orderable items //Output: A heap H[1..n