Queap
કોમ્પ્યુટર વિજ્ઞાનમાં, કતાર એ અગ્રતા કતાર માહિતી માળખું છે. ડેટા સ્ટ્રક્ચર મનસ્વી તત્વોને દાખલ કરવા અને કાઢી નાખવાની મંજૂરી આપે છે, તેમજ સર્વોચ્ચ-અગ્રતા તત્વની પુનઃપ્રાપ્તિની મંજૂરી આપે છે. દરેક કાઢી નાંખવામાં દૂર કરેલી વસ્તુ કરતાં લાંબા સમયથી માળખામાં રહેલી વસ્તુઓની સંખ્યામાં ઋણમુક્ત સમય લઘુગણક લે છે. દાખલ કરવામાં સતત ઋણમુક્ત સમય લાગે છે. ડેટા સ્ટ્રક્ચરમાં બમણી રીતે જોડાયેલી સૂચિ અને 2-4 વૃક્ષ ડેટા સ્ટ્રક્ચરનો સમાવેશ થાય છે, જેમાં દરેક તેના લઘુત્તમ-પ્રાથમિકતા તત્વનો ટ્રેક રાખવા માટે સુધારેલ છે. માળખાની મૂળભૂત કામગીરી એ છે કે બમણું જોડાયેલ સૂચિમાં નવા દાખલ કરેલા તત્વોને ત્યાં સુધી રાખવા, જ્યાં સુધી કાઢી નાંખવાથી સૂચિમાંથી એક વસ્તુ દૂર ન થાય, તે સમયે તે બધાને 2-4 વૃક્ષમાં ખસેડવામાં આવે છે. 2-4 વૃક્ષ તેના તત્વોને વધુ પરંપરાગત અગ્રતા-ક્રમાંકિત ક્રમને બદલે નિવેશ ક્રમમાં સંગ્રહિત કરે છે. માહિતી માળખું અને તેનું નામ બંને જ્હોન આઈકોનો અને સ્ટીફન લેંગરમેન દ્વારા તૈયાર કરવામાં આવ્યા હતા. વર્ણન એક કતાર એ એક પ્રાથમિક કતાર છે જે ઓ (1) ઋણમુક્ત સમયમાં તત્વોને દાખલ કરે છે, અને ઓ (લોગ (કે + 2)) માં લઘુતમ તત્વને દૂર કરે છે જો ત્યાં કે વસ્તુઓ હોય જે ઢગલામાં કાઢવાના તત્વ કરતાં લાંબા સમયથી હોય. કતારમાં કતાર મિલકત તરીકે ઓળખાતી મિલકત હોય છેઃ તત્વ x માટે શોધવાનો સમય O (lg q (x)) છે જ્યાં q (x) એ n − 1 − w (x) ની બરાબર છે અને w (x) એ અલગ વસ્તુઓની સંખ્યા છે જે શોધ, દાખલ કરવા અથવા કાઢી નાખવા જેવી કામગીરીઓ દ્વારા એક્સેસ કરવામાં આવી છે. q (x) ને વ્યાખ્યાયિત કરવામાં આવે છે કે x ની છેલ્લી ઍક્સેસથી કેટલા ઘટકો ઍક્સેસ કરવામાં આવ્યા નથી. ખરેખર, કતારની મિલકત એ સ્પ્લે ટ્રી વર્કિંગ સેટ પ્રોપર્ટીના પૂરક છેઃ તત્વ x શોધવાનો સમય O (lg w (x)) છે. કતારને બે માહિતી માળખાઓ દ્વારા રજૂ કરી શકાય છેઃ બમણી રીતે જોડાયેલી સૂચિ અને 2-4 વૃક્ષનું સુધારેલું સંસ્કરણ. બમણી રીતે જોડાયેલી સૂચિ, એલ, નો ઉપયોગ ઇન્સર્ટ અને લોકેટ-મિન કામગીરીની શ્રેણી માટે થાય છે. કતાર સૂચિમાં સંગ્રહિત લઘુત્તમ તત્વ માટે નિર્દેશક રાખે છે. સૂચિ l માં તત્વ x ઉમેરવા માટે, તત્વ x ને સૂચિના અંતમાં ઉમેરવામાં આવે છે અને તત્વ x માં બીટ ચલ એક પર સેટ કરવામાં આવે છે. આ ઓપરેશન એ નક્કી કરવા માટે કરવામાં આવે છે કે તત્વ ક્યાં તો સૂચિમાં છે અથવા 2-4 વૃક્ષમાં છે. જ્યારે કાઢી નાંખવાની કામગીરી થાય છે ત્યારે 2-4 વૃક્ષનો ઉપયોગ થાય છે. જો વસ્તુ x પહેલેથી જ વૃક્ષ T માં હોય, તો વસ્તુને 2-4 વૃક્ષ કાઢી નાંખવાની કામગીરીનો ઉપયોગ કરીને દૂર કરવામાં આવે છે. નહિંતર, વસ્તુ x સૂચિ L માં છે (બીટ ચલ સેટ છે કે નહીં તે ચકાસીને કરવામાં આવે છે). સૂચિ L માં સંગ્રહિત તમામ ઘટકો પછી 2-4 વૃક્ષમાં ઉમેરવામાં આવે છે, દરેક તત્વના બીટ ચલને શૂન્ય પર સેટ કરે છે. પછી x ને T માંથી દૂર કરવામાં આવે છે. એક કતાર માત્ર 2-4 વૃક્ષ માળખાના ગુણધર્મોનો ઉપયોગ કરે છે, શોધ વૃક્ષનો નહીં. સુધારેલ 2-4 વૃક્ષનું માળખું નીચે મુજબ છે. ધારો કે સૂચિ L માં તત્વોનો નીચેનો સમૂહ છેઃ જ્યારે કાઢી નાંખવાની કામગીરી હાથ ધરવામાં આવે છે, ત્યારે L માં સંગ્રહિત તત્વોનો સમૂહ તે ક્રમમાં 2-4 વૃક્ષના પાંદડાઓમાં ઉમેરવામાં આવે છે, જે અનંત ચાવી ધરાવતા ડમી પર્ણ દ્વારા આગળ વધે છે. ટીના દરેક આંતરિક નોડમાં એક નિર્દેશક હોય છે, જે સબટ્રી વીમાં સૌથી નાની વસ્તુ તરફ નિર્દેશ કરે છે. રુટથી પાથ પી પર દરેક આંતરિક નોડમાં નિર્દેશક હોય છે, જે સૌથી નાની કી તરફ નિર્દેશ કરે છે. પાથ P પરના દરેક આંતરિક નોડના પોઇન્ટરને અવગણવામાં આવે છે. કતારમાં એક નિર્દેશક હોય છે, જે ટીમાં સૌથી નાના તત્વ તરફ નિર્દેશ કરે છે. કતારોના ઉપયોગમાં ઉચ્ચ પ્રાથમિકતા ધરાવતી ઘટનાઓનો એક અનોખો સમૂહ અને પ્રક્રિયા માટે સર્વોચ્ચ પ્રાથમિકતા ધરાવતી ઘટનાનું નિષ્કર્ષણ સામેલ છે. કામગીરીઓ એમ. આઈ. એન. એલ. ને એક નિર્દેશક બનવા દો જે બમણી રીતે જોડાયેલી સૂચિ એલમાં લઘુતમ તત્વ તરફ નિર્દેશ કરે છે, 2-4 વૃક્ષમાં સંગ્રહિત લઘુતમ તત્વ હોય, ટી, કે એ ટીમાં સંગ્રહિત તત્વોની સંખ્યા હોય અને એન એ ક્યુઅપ ક્યૂમાં સંગ્રહિત તત્વોની કુલ સંખ્યા હોય. કામગીરીઓ નીચે મુજબ છેઃ નવી (ક્યૂ): નવી ખાલી કતારને શરૂ કરે છે. ખાલી બમણી લિંક કરેલી સૂચિ L અને 2-4 વૃક્ષ T ને પ્રારંભ કરો. k અને n ને શૂન્ય પર સેટ કરો. દાખલ કરો (ક્યૂ, એક્સ): ક્વીપમાં તત્વ x ઉમેરો ક્યૂ. સૂચિમાં તત્વ x દાખલ કરો એલ. તત્વ x માં બીટને એક પર સેટ કરો તે દર્શાવવા માટે કે તત્વ સૂચિમાં છે એલ. જો સૂચિમાં x સૌથી નાનું તત્વ હોય તો મિનિએલ નિર્દેશકને અપડેટ કરો. n માં 1 નો વધારો. ન્યુનત્તમ (ક્યૂ): ક્યુઅપ ક્યૂમાંથી સૌથી નાના તત્વ માટે નિર્દેશકને પુનઃપ્રાપ્ત કરો. જો કી (મિનિએલ) <કી () હોય, તો મિનિએલ પરત કરો. નહીં તો પાછા આવી જાવ. કાઢી નાંખો (Q, x): ક્વીપ Q માંથી ઘટક x ને દૂર કરો. જો ઘટક x નો બીટ એક પર સેટ કરેલ હોય, તો તત્વ સૂચિ L માં સંગ્રહિત થાય છે. L થી T સુધીના તમામ ઘટકોને ઉમેરો, દરેક ઘટકનો બીટ શૂન્ય પર સેટ કરો. દરેક તત્વને 2-4 વૃક્ષની ઇન્સર્ટ ઓપરેશનનો ઉપયોગ કરીને ટીના જમણા સૌથી વધુ બાળકના પેરેન્ટમાં ઉમેરવામાં આવે છે. L ખાલી થઈ જાય છે. બધા નોડ્સ v માટે પોઇન્ટર અપડેટ કરો જેમના બાળકો નવા/સંશોધિત છે, અને જ્યાં સુધી પેરેન્ટ રુટની બરાબર ન હોય ત્યાં સુધી આગામી પેરેન્ટ સાથે પ્રક્રિયાને પુનરાવર્તન કરો. રુટથી નોડ સુધી ચાલો અને મૂલ્યોને અપડેટ કરો. k ને n ની બરાબર સુયોજિત કરો. જો x તત્વનો બીટ શૂન્ય પર સુયોજિત હોય, તો x એ T નું પાન છે. 2-4 વૃક્ષ કાઢી નાંખવાની કામગીરીનો ઉપયોગ કરીને x કાઢી નાંખો. નોડ x થી શરૂ કરીને, ટી થી નોડ સુધી ચાલો, અપડેટ કરો અને પોઇન્ટર કરો. n અને k ને 1 વડે ઘટાડો. ડીલીટમિન (ક્યૂ): ક્યુઅપ ક્યૂમાંથી સૌથી નાનું તત્વ કાઢી નાંખો અને પરત કરો. ન્યુનત્તમ (ક્યૂ) કામગીરીને બોલાવો. ઓપરેશન મિનિમ પરત કરે છે. કાઢી નાંખો (ક્યૂ, મિનિમ) ઓપરેશનનો ઉપયોગ કરો. મિનિમ પરત કરો. ક્લીનઅપ (ક્યૂ): સૂચિ એલ અને વૃક્ષ ટીમાંના તમામ ઘટકોને કાઢી નાંખો. સૂચિ એલના પ્રથમ ઘટકથી શરૂ કરીને, દરેક નોડને કાઢીને સૂચિને પાર કરો. વૃક્ષ T ના મૂળથી શરૂ કરીને, વૃક્ષમાં દરેક નોડને કાઢીને, પોસ્ટ-ઓર્ડર ટ્રાવર્સલ અલ્ગોરિધમનો ઉપયોગ કરીને વૃક્ષને પાર કરો. વિશ્લેષણ ચાલુ સમયનું વિશ્લેષણ ઋણમુક્ત વિશ્લેષણનો ઉપયોગ કરીને કરવામાં આવે છે. ક્વેપ Q માટે પોટેન્શિયલ ફંક્શન ક્યાં હશે. દાખલ કરો (ક્યૂ, એક્સ): કામગીરીની કિંમત ઓ (1) છે. સૂચિ L નું કદ એકથી વધે છે, સંભવિત અમુક સતત વધે છે c. લઘુત્તમ (Q): કામગીરી ડેટા માળખામાં ફેરફાર કરતી નથી તેથી ઋણમુક્ત ખર્ચ તેની વાસ્તવિક કિંમત, O (1) ની બરાબર છે. કાઢી નાંખો (ક્યૂ, એક્સ): બે કિસ્સાઓ છે. કેસ 1 જો x વૃક્ષ T માં હોય, તો પછી ઋણમુક્ત ખર્ચમાં ફેરફાર કરવામાં આવતો નથી. કાઢી નાંખવાની ક્રિયા ઓ (1) એમોર્ટાઇઝ્ડ 2-4 વૃક્ષ છે. કારણ કે x ને વૃક્ષમાંથી દૂર કરવામાં આવ્યું હતું, અને પોઇન્ટરને અપડેટ કરવાની જરૂર પડી શકે છે. વધુમાં વધુ, સુધારાઓ હશે. કેસ 2 જો x સૂચિ L માં હોય, તો પછી L માંથી તમામ ઘટકો T માં દાખલ કરવામાં આવે છે. આની કિંમત અમુક અચળાંક a ની હોય છે, જે 2-4 વૃક્ષ પર ઋણમુક્ત થાય છે. અને પોઇન્ટર દાખલ કર્યા પછી અને અપડેટ કર્યા પછી, ખર્ચવામાં આવેલો કુલ સમય તેના દ્વારા બંધાયેલો હોય છે. બીજી ક્રિયા એ છે કે T માંથી x ને કાઢી નાખવું, અને x થી x તરફના માર્ગ પર ચાલવું, સુધારા અને મૂલ્યો. મોટાભાગનો સમય પસાર થાય છે. જો, તો પછી ઋણમુક્ત ખર્ચ હશે. કાઢી નાંખો (ક્યૂ, એક્સ): લઘુતમ (ક્યૂ) અને કાઢી નાંખો (ક્યૂ, એક્સ) ના ઋણમુક્ત ખર્ચનો ઉમેરો છે, જે છે. કોડ ઉદાહરણ ક્વિપનું એક નાનું જાવા અમલીકરણઃ સાર્વજનિક વર્ગ ક્વિપ {સાર્વજનિક ઇન્ટ એન, કે; સાર્વજનિક સૂચિ <એલિમેન્ટ> એલ;// એલિમેન્ટ એ સામાન્ય ડેટા પ્રકાર છે. સાર્વજનિક ક્વીપટ્રી ટી;// એક 2-4 વૃક્ષ, ક્વીપ હેતુ માટે સુધારેલ જાહેર ઘટક એમ. એન. એલ.; ખાનગી ક્વીપ () {એન = 0; કે = 0; એલ = નવી લિન્ક્ડ લિસ્ટ <એલિમેન્ટ> (); ટી = નવી ક્વીપટ્રી ();} જાહેર સ્થિર ક્વિપ નવી () {નવી ક્વિપ () પરત કરો;} જાહેર સ્થિર શૂન્ય દાખલ કરો (ક્વિપ ક્યૂ, એલિમેન્ટ એક્સ) {જો (ક્યૂ. એન = = 0) Q.minL = x; Q.l.add (x); x.inList = સાચું; જો (x.compareTo (Q.minL) <0) Q.minL = x;} જાહેર સ્થિર તત્વ લઘુત્તમ (ક્વિપ ક્યૂ) { જો (Q.minL.compareTo (Q.t.x0.cv. કી) <0) રીટર્ન કરે Q.minL; રીટર્ન કરે Q.t.x0.cv. કી;} પબ્લિક સ્ટેટિક વોઈડ ડીલીટ (ક્વીપ ક્યૂ, ક્વીપનોડ એક્સ) {Q.t.deleteLeaf (એક્સ);-- Q. n;-- Q. k;} પબ્લિક સ્ટેટિક વોઈડ ડીલીટ (ક્વીપ ક્યૂ, એલિમેન્ટ એક્સ) {ક્વીપનોડ એન; જો (x.inList) {// સૂચિમાંના તમામ ઘટકોની યાદી ખોટી n = Q.t.insertList (Q. l, x); Q. k = Q. n; કાઢી નાંખો (Q, n); અન્યથા જો ((n = Q.t.x0.cv).