• C

# Priority Queue Implementation using Binary Tree

Using C programming Languague, can
an Ascending Priority Queue be
implemented using an implicit array
representation of a Binary Tree ? How ?
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Author Commented:
0
Author Commented:
Edited text of question.
0
Commented:
> .. can an ..
yes
> How?
just use the btree algorithm
0
Author Commented:
does the front and rear pointers play any part in the
implementation,  or do we have to consider it at all ?

Can I get references for the btree algorithm ?

0
Commented:
what you need is a HEAP.
the heap is classic implemetion of a queue.

the heap rule is that every father
is bigger then is sons.
therefor, the top most one is the highest.

because a heap is a full tree, it can easly implemented with an array
when for a father with index i
his left son has an index of 2*i
and right son has an index of 2*i+1

after extracting the max (index 1...)
you should take care by the
heapify procedure that the heap rule
is maintened.
the cost is only log(n).

any questions...

Yair

0
Commented:
ofcoure the can be dynamicly changed
by adding new priorites to the heap,
while working with it.

the heapify procedure take care
for an index i that he is bigger then his sons.
if not, it will swap with is bigest son and the procedure will call itself to the swapped son index - to preserve the heap property....

0
Author Commented:
But the necessity is a Binary tree algorithm,
an effecient Binary tree algorithm which implements the
ascending priority queue using the implicit representation
of a Binary Tree.  I need references for the alogritm as well!
0
Commented:
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
did you understood my answer ?

you need a heap structure not a binaric tree. a heap is ALSO a FULL binaric tree, AND it is represented in an array
(no pointers !) because its a full tree.

in a heap the top prioruty is alway at the top. when it is extracted, the next one takes its place.
as I said before, the cost is log(n)
(very cheap)

Yair

0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.