# Heap Sort

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(log*n*) 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`)).

Posted on July 7, 2011, in Uncategorized. Bookmark the permalink. Leave a comment.

## Leave a comment

## Comments 0