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.

--