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(logn) time, using a binary heap, by following this algorithm:


  1. Add the element to the bottom level of the heap.
  2. Compare the added element with its parent; if they are in the correct order, stop.
  3. 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)).

Advertisements

About ramyabkrishna

I am Ramya B Krishna doing MCA at GEC Thrissur. I am now in the process of taking a Leap into the world of Linux and hoping to do a few projects as well.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: