A heap is a specialized tree-based data structure that satisfies
the heap property: if B is a child node of A, then key(A) ≥ key(B). This
implies that an element with the greatest key is always in the root node,
and so such a heap is sometimes called a max-heap. Alternatively, if the
comparison is reversed, the smallest element is always in the root node,
which results in a min-heap. The heap is an efficient implementation of an
abstract data type called a priority queue. Heaps are crucial in several
efficient graph algorithms such as Dijkstra’s algorithm, and in the sorting
algorithm heap sort.
Heap sort is an implementation of a binary heap. Once we
have implemented the heap,we will easily deduce heap sort.The data
structure of the heap sort algorithm is a heap. The data sequence to be
sorted is stored as the labels of the binary tree.For each element at index i
in the tree:its left child is at index 2i+1,its right child is at index 2i+2 and its
parent is at (i-1)/2.If the provided list is not empty,it will be heapified and new
elements can be inserted to the heap.A new element will be first put at the
end of the tree,then pulled up until the tree satisfies the heap priority.
To add an element to a heap we must perform an up-heap operation also
known as bubble-up in order to restore the heap property. We can do this
in O(logn) time, using a binary heap, by following this algorithm:
- Add the element to the bottom level of the heap.
- Compare the added element with its parent; if they are in the correct order, stop.
- If not, swap the element with its parent and return to the previous step.
An almost complete binary tree with n vertices has a depth of at most log(n).
This approach requires O(n.logn) time because each insertion takes
O(n.logn) time and there are n elements.Thus,the time complexity of
heap sort is T (n)=O(n·log(n)).