• 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 ?
0
arunma_2000
Asked:
arunma_2000
1 Solution
 
arunma_2000Author Commented:
no  more comments
0
 
arunma_2000Author Commented:
Edited text of question.
0
 
ahoffmannCommented:
> .. can an ..
yes
> How?
just use the btree algorithm
0
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 ?

0
 
yairyCommented:
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
 
yairyCommented:
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
 
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!
0
 
yairyCommented:
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

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