• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 594
  • Last Modified:

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 ?
1 Solution
arunma_2000Author Commented:
no  more comments
arunma_2000Author Commented:
Edited text of question.
> .. can an ..
> How?
just use the btree algorithm
The Lifecycle Approach to Managing Security Policy

Managing application connectivity and security policies can be achieved more effectively when following a framework that automates repeatable processes and ensures that the right activities are performed in the right order.

arunma_2000Author 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 ?

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...


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....

arunma_2000Author 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!
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)



Featured Post

The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now