Heap Tree and Heap Sort
Introduction
- A heap is a binary tree with a key value in each node satisfying following properties:
- All the leaves of the heap tree are on adjacent levels.
- All the leaves in the lowest level occur in the left to right, and all the levels except lowest are filled.
The key in the parent node is greater than the keys in
its children (if any); left and right subtrees are again heaps
Heap
Sort
Heap sort occurs in two phases. A heap tree is created using all the keys of the array in the first phase, then in the second phase, keys of the heap tree are removed from root one by one and stored in array maintaing the properties of the heap tree. Heap sort sorts a contiguous list of lenght n with O(n logn) comparisons and movements of the keys.Â
A Heap tree Example: An array of keys, and its
corresponding heap tree, value of index i starts with 1. The first element of
the heap tree is root element and its index is 1; right and left children of
root are given by positions: 2i and 2i+1. In the given example root has 22 as
key and its left and right children lies at 2i = 2 * 1 =2 and 2i+1 = 2*1+1=3
positions.
Sorting array using
Heap Sort: Array of data: 22, 33, 11, 55, 17.(Array is sorted in descending
order in this example, as the elements are stored from front to rear. If
elements are stored from rear to front then the array will be sorted in
ascending order.
First
Phase: Create a max heap with given data.
