Heap Sort - nlog(n) ??
Author Message Heap Sort - nlog(n) ??

Hello everybody !!

I have a doubt regarding a sorting technique called Heap Sort.
Refer - "Data Structures in C - Tanenbaum".

I understand that heap sort is O(n log n).
Each Insertion and deletion are both O( log n), since an almost
complete binary tree has log(n)+1 levels and atmost one node is accessed
in each level.

But, is it assured that the insertion algorithm will always result in
an
"Almost Complete Binary" tree ??
Refer - "DS in C - Tanenbaum , page 252"

Regards,
Abhijit
--

Sun, 18 May 2003 09:04:58 GMT  Heap Sort - nlog(n) ??

Quote:
> Hello everybody !!

>   I have a doubt regarding a sorting technique called Heap Sort.
>   Refer - "Data Structures in C - Tanenbaum".

>   I understand that heap sort is O(n log n).
>   Each Insertion and deletion are both O( log n), since an almost
> complete binary tree has log(n)+1 levels and atmost one node is accessed
> in each level.

>  But, is it assured that the insertion algorithm will always result in
> an
> "Almost Complete Binary" tree ??
> Refer - "DS in C - Tanenbaum , page 252"

The whole purpose of creating a "heap" is to ensure that you have an "almost
complete binary tree". For example, create a "heap" out of an array,
h[1..N], in which:

The parent of a node h[n] is at h[n/2]
The right child of a node h[n] is at h[2n]
The left child of a node h[n] is at h[2n+1]

It is always possible to rearrange an array into such a heap in O(nlog(n))
time (some child nodes are beyond the end of the array, therefore they are
empty).
--

Sun, 18 May 2003 03:00:00 GMT  Heap Sort - nlog(n) ??

Quote:

>   I understand that heap sort is O(n log n).
>   Each Insertion and deletion are both O( log n), since an almost
> complete binary tree has log(n)+1 levels and atmost one node is accessed
> in each level.

>  But, is it assured that the insertion algorithm will always result in
> an
> "Almost Complete Binary" tree ??
> Refer - "DS in C - Tanenbaum , page 252"

Yep, it is assured. Think of this heap as linear array where the
nodes are stored. Node #0 is the root of the tree. The children
of a node i (if present) are 2*i+1 and 2*i+2. All the nodes are
stored adjacent in the array; this implies for a treee with
2^(m-1) < n < 2^m nodes that the nodes n+1, n+2 ... 2^m are missing,
which are the rightmost leave nodes in the tree. Hence the
tree is 'almost complete'.

kind regards,

--

Sun, 18 May 2003 03:00:00 GMT  Heap Sort - nlog(n) ??

Quote:

> Hello everybody !!
>   I have a doubt regarding a sorting technique called Heap Sort.

... and I have a doubt that this question is within the topic of this
newsgroup...

Anyway:

Quote:
>  But, is it assured that the insertion algorithm will always result
> in an "Almost Complete Binary" tree ??

No. A Heap is *not* a binary tree --- at least not one of the kind you
usually have in a sorting&searching algorithm. The ordering of
elements between a parent and its children is different. For a binary
tree, it's

left child < parent < right child

For a heap, it's

both childs < parent.

This makes the heap structure simpler to manage than a binary tree,
and avoids the bad worst-case behaviour of binary trees that they can
degenerate into a linear list.

It is guaranteed that a heap is always an almost complete binary tree,
topologically: new elements are always added at the 'lower right'
position.
--

Even if all the snow were burnt, ashes would remain.
--

Sun, 18 May 2003 03:00:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages