Linux and Technology blog

August 17, 2006

Heapsort

Filed under: Tutorials — rakeshvk @ 6:02 pm

With its time complexity of O(n log(n)) heapsort is optimal. It utilizes a special data structure called heap. This data structure is explained in the following.

Basics

Definition: Let T = (VE) an almost complete binary tree with a vertex labelling a : V arrow M that assigns to each vertex u a label a(u) from an ordered set (M<=).

A vertex u element V has the heap property if it has no direct descendant with a greater label, i.e.

for all v element V  :  (uvelement E   implies   a(u>= a(v)

T is a heap if all vertices have the heap property, i.e.

for all (uvelement E  :  a(u>= a(v)

We call T a semi-heap if all vertices except possibly the root r have the heap property, i.e.

for all (uvelement E,  unot equalr  :  a(u>= a(v)

Example:

Heap with n = 10 vertices
 
 
Figure 1:  Heap with n = 10 vertices
 

Observe that each leaf automatically has the heap property regardless of its label, since it has no descendants. >>>>

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

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

Blog at WordPress.com.

%d bloggers like this: