Initialising a heap in O(n) complexity

[infinitecmdz]

Hey guys,

I have a problem in which I have to initialize a deap with n elments and this function must be run in O(n) time. BTW, a deap is heap which has both a Min Heap and a Max Heap. Any help on this would highly be appreciated..



Thanx


yours

Sid

[mehdi62b]

I assume a deap is the same as min-max heap Min-Max Heaps
Given a set S of values, a min-max heap on S is a
binary tree T with the following properties:
1) T has the heap-shape
2) T is min-max ordered: values stored at nodes on
even (odd) levels are smaller (greater) than or equal
to the values stored at their descendants (if any)
where the root is at level zero. Thus, the smallest
value of S is stored at the root of T, whereas the
largest value is stored at one of the root’s children
http://kmh.ync.ac.kr/comScience/general/DS/Heap/gifs/minmaxhe.gif

firstly have a look at this thread :

how could the comlexity of build heap coverges from O(nlog n) to O(n) (http://www.codeguru.com/forum/showthread.php?t=356744)

so just its shift-down function should be changedprocedure ShiftDown(i)
- - i is the position in the array
if i is on a min level then
ShiftDownMin(i)
else
ShiftDownMax(i)
endif

procedure ShiftDownMin(i)
if A[i] has children then
m := index of smallest of the
children and grandchildren
(if any) of A[i]
if A[m] is a grandchild of A[i] then
if A[m] < A[i] then
swap A[i] and A[m]
if A[m] > A[parent(m)] then
swap A[m] and A[parent(m)]
endif
ShiftDownMin(m)
endif
else {A[m] is a child of A[i]]
if A[m] < A[i] then
swap A[i] and A[m]
endif
endifThe procedure ShiftDownMax is the same except that the relational operators are inverted.