Pagoda data structure(Priority Queue)
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 l1>=r1 , the next step is
the case l1<=r1 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.
More Articles of nabin mondal:
| Name | Views | Likes |
|---|---|---|
| C++ Boost::Iterators::Generator Iterator Adaptor | 460 | 1 |
| Pagoda data structure(Priority Queue) | 913 | 2 |
| C++ boost::Iterators::Counting Iterators | 610 | 2 |
| C++ boost::Iterator::Filter Iterator | 1174 | 2 |
Comments
Kumar
25-Oct-2019 08:30:58 PM