PAGODA DATA STRUCTURE(PRIORITY QUEUE)

*Introduction *: - Pagoda data structure is a data structure which is used to implement Priority Queues in a very efficient manner where our efficiency is the measure of the *average running time * of the various algorithms. The given algorithms process an arbitrary sequence of n operations MIN, INSERT and EXTRACT in Linear average time 0(n), and a sequence of n INSERT in linear worst case time 0(n).

__1 . Pagoda(Data Structure) : - __*Efficient** *processing of binary tournaments requires access to the leaves of the right and left branches . The pagoda is a representation of binary trees with two pointers left(L) and right(R) per node, which allows for this treatment in a uniform manner ; pointers g and d are defined by the following rules :-

(i) Root : if Rt is the root of the tree T, R(Rt) points to the bottom of the right branch of T, and L(rt) to the bottom of the left branch of T .

(ii) Left son : if K is a left-son in T, R(k) points to the father of k and L(k) to the bottom of the right branch starting at k .

(iii) Right son : if k is a right son in T, d(k) points to its father and g(k) to the bottom of the left branch starting at k. The

2. The Detailed explanation:-

__1.Union:-__

It is natural to start the description of the remaining primitives by UNION, since the other three can be reduced to it . Let

R and

L be two pagodas which are to be merged into

F . Initially,

F=NULL and result

F is constructed by a bottom-up merge of

rb(R) and

lb(D) . If

BG and

BD point to the leaves of

rb(R) and

lb(L), the situation at a typical step of the merge is:-

if l_{1}>=r_{1} , the next step is

the case l_{1}<=r_{1} is treated in a symetrical fashion . The algorithm terminates when one of the arguments, say l

becomes empty.

*2. INSERT:-* By regarding a single key p as a pagoda where the right and the left link is pointed to itself, we can treat INSERT as the special case of union where the second Pagoda has only one node

*3.DELETE(EXTRACTION):-*Extraction of an arbitrary key k, designated by its address in the structure, is possible in pagodas without extra links . To extract k, it is sufficient to find links to the right and left branches of the sub-trees L and R having k for root . Once these pointers are found, we proceed as in the extraction of the minimum by performing the union of R and L in that order . That randomness is preserved under this operation follows from the same argument as before . One of the links to R or L can be found in r(k) or l(k) : it is r(k) if and only priority (r(k)) > priority (k) ; in this case, the other link is found by following the upwards links 1(k), 11(k), . . ., until we find a key x for which priority (1(x)) > priority (x)) ; the required link .

For Example, lets take the extraction key is 3 then according to the algorithm the conversion will be like :-

__4. C++ Code :-____4.OUTPUT:-__

*4 . Its comparison with heap data structure : - *Pagodas provide the most efficient average time implementation for priority queues ; for non merge-able priority queues, performances are close to those of heaps, with advantages and disadvantages for both structures : heaps use less memory but require contiguous storage allocation ; heaps have a guaranteed O(log n) worst case for insertion versus Q(n) worst case for pagodas ; on the other hand, the worst case for n successive insertions is 0(n log n) in a heap and 0(n) in a pagoda . Pagodas allow to merge priority queues, an operation which is not possible with heaps . In both pagodas and heaps, one can EXTRACT an arbitrary key in average a time 0(1.

Conclusion:- In this article we learnt the pagoda data structure, hope you have understood the topic well.

## Comments

## Kumar

25-Oct-2019 08:30:58 PM