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  
 
 [ 4 post ] 

 Relevant Pages 

1. HEAP[dllhost.exe]: HEAP: Free Heap block 1e32c28 modified at 1e32dc4 after it was freed

2. Heap Sort

3. Heap Sorting

4. Heap-sort

5. Looking for a good heap sort

6. heap sort

7. Heap Sort

8. Binomial heaps / Fibonacci heaps

9. (ATL) COM dll heap vs CRT heap

10. HEAP error: Free heap block xxx mdofied at xxx

11. Invalid heap signature for heap

12. Heap errors when stressing Automation, _bstr_t, and watching heap blocks

 

 
Powered by phpBB® Forum Software