Kinetic heap
કાઇનેટિક હીપ એ કાઇનેટિક ડેટા સ્ટ્રક્ચર છે, જે ઢગલાના કાઇનેટાઇઝેશન દ્વારા મેળવવામાં આવે છે. તે એવા ઘટકો (પ્રાથમિકતાઓ સાથે સંકળાયેલી ચાવીઓ) ને સંગ્રહિત કરવા માટે રચાયેલ છે જ્યાં સમયના સતત કાર્ય તરીકે પ્રાથમિકતા બદલાઈ રહી છે. ગતિશીલ અગ્રતા કતારના પ્રકાર તરીકે, તે તેમાં સંગ્રહિત મહત્તમ અગ્રતા તત્વ જાળવે છે. કાઇનેટિક હીપ ડેટા સ્ટ્રક્ચર તત્વોને એક વૃક્ષ તરીકે સંગ્રહિત કરીને કામ કરે છે જે નીચેના હીપ પ્રોપર્ટીને સંતોષે છે જો તે ચાઈલ્ડ નોડ હોય, તો પછી તત્વની પ્રાથમિકતા તત્વની પ્રાથમિકતા કરતા વધારે હોવી જોઈએ. આ ઢગલાના ગુણધર્મને દરેક ધાર પર પ્રમાણપત્રોનો ઉપયોગ કરીને લાગુ કરવામાં આવે છે, તેથી, અન્ય ગતિશીલ માહિતી માળખાઓની જેમ, ગતિશીલ ઢગલામાં પણ પ્રમાણપત્ર નિષ્ફળતાના સમયને જાળવવા માટે અગ્રતા કતાર (ઇવેન્ટ કતાર) હોય છે. અમલીકરણ અને કામગીરી નોડ્સની દરેક જોડી માટે પ્રમાણપત્ર [] સાથે વૃદ્ધિ કરીને નિયમિત ઢગલાને ગતિમાન કરી શકાય છે, જેમ કે નોડ્સનો ચાઈલ્ડ નોડ. જો નોડ પર સંગ્રહિત મૂલ્ય સમયનું કાર્ય હોય, તો આ પ્રમાણપત્ર માત્ર ત્યારે જ માન્ય છે. આમ, આ પ્રમાણપત્રની નિષ્ફળતા ઇવેન્ટ કતારમાં આવા સમયે સુનિશ્ચિત થવી જોઈએ કે જેથી. તમામ પ્રમાણપત્ર નિષ્ફળતાઓ "ઇવેન્ટ કતાર" પર સુનિશ્ચિત થયેલ છે, જે એક કાર્યક્ષમ અગ્રતા કતાર હોવાનું માનવામાં આવે છે જેની કામગીરીમાં સમય લાગે છે. પ્રમાણપત્રની નિષ્ફળતાઓનો સામનો કરવો જ્યારે પ્રમાણપત્ર [] નિષ્ફળ જાય છે, ત્યારે ડેટા સ્ટ્રક્ચરને અદલાબદલી કરવી જોઈએ અને ઢગલામાં હોવું જોઈએ, અને તે પ્રમાણપત્રોને અપડેટ કરવું જોઈએ જેમાં તે દરેક હાજર હતા. ઉદાહરણ તરીકે, જો (ચાઈલ્ડ નોડ્સ અને સાથે) ચાઈલ્ડ નોડ (ચાઈલ્ડ નોડ્સ અને પેરેન્ટ નોડ સાથે) હોય, અને પ્રમાણપત્ર [] નિષ્ફળ જાય, તો ડેટા સ્ટ્રક્ચરને અદલાબદલી કરવી જોઈએ અને પછી જૂના પ્રમાણપત્રો (અને અનુરૂપ સુનિશ્ચિત ઘટનાઓ) [], [], [], [], [] ને નવા પ્રમાણપત્રો [], [], [], [] અને [] સાથે બદલવું જોઈએ. આમ, ઘટનાઓની બિન-અધોગતિ (એક જ સમયે કોઈ બે ઘટનાઓ થતી નથી) ધારીને, સૌથી ખરાબ કિસ્સામાં પણ માત્ર સતત સંખ્યાબંધ ઘટનાઓને નિર્ધારિત કરવાની અને ફરીથી નિર્ધારિત કરવાની જરૂર છે. ક્રિયાઓ ગતિશીલ ઢગલા નીચેની કામગીરીઓને ટેકો આપે છેઃ ખાલી ગતિશીલ ઢગલા બનાવો (અથવા શોધો-લઘુત્તમ): વર્તમાન વર્ચ્યુઅલ સમયે ઢગલામાં સંગ્રહિત (અથવા a માટે) મૂલ્ય પરત કરો. : વર્તમાન વર્ચ્યુઅલ સમયે ગતિશીલ ઢગલામાં કી દાખલ કરો, જેનું મૂલ્ય સમયના સતત કાર્ય તરીકે બદલાય છે. નિવેશ સમયસર સામાન્ય ઢગલાની જેમ કરવામાં આવે છે, પરંતુ પરિણામે પ્રમાણપત્રોને બદલવાની જરૂર પડી શકે છે, તેથી પ્રમાણપત્ર નિષ્ફળતાના પુનઃનિર્ધારણ માટેનો કુલ સમય વર્તમાન વર્ચ્યુઅલ સમયે કીને કાઢી નાખવામાં આવે છે. કાઢી નાંખવાનું સામાન્ય સમયની જેમ કરવામાં આવે છે, પરંતુ પરિણામે પ્રમાણપત્રોને બદલવાની જરૂર પડી શકે છે, તેથી પ્રમાણપત્રની નિષ્ફળતાઓને ફરીથી સુનિશ્ચિત કરવા માટેનો કુલ સમય છે. પરફોર્મન્સ કાઇનેટિક હીપ્સ બાશ એટ અલ દ્વારા વ્યાખ્યાયિત કાઇનેટિક ડેટા સ્ટ્રક્ચર ક્વોલિટીના ચાર મેટ્રિક્સ (રિસ્પોન્સિવનેસ, લોકાલિટી, કોમ્પેક્ટનેસ અને એફિશિયન્સી) અનુસાર સારું પ્રદર્શન કરે છે. પ્રથમ ત્રણ ગુણોનું વિશ્લેષણ સીધું છેઃ પ્રતિભાવઃ એક ગતિશીલ ઢગલા પ્રતિભાવશીલ છે, કારણ કે દરેક પ્રમાણપત્રની નિષ્ફળતા સંબંધિત કીઓને અદલાબદલી કરવાનું કારણ બને છે અને સૌથી ખરાબ કિસ્સામાં માત્ર થોડા પ્રમાણપત્રોને બદલવામાં આવે છે. સ્થાનઃ દરેક નોડ તેના પેરેન્ટ નોડ અને બે ચાઈલ્ડ નોડ (જો હાજર હોય તો) સાથે એક પ્રમાણપત્રમાં હાજર હોય છે, જેનો અર્થ છે કે દરેક નોડ સૌથી ખરાબ કિસ્સામાં કુલ ત્રણ સુનિશ્ચિત ઘટનાઓમાં સામેલ થઈ શકે છે, આમ ગતિશીલ ઢગલાઓ સ્થાનિક હોય છે. કોમ્પેક્ટનેસઃ ઢગલાની દરેક ધાર બરાબર એક સુનિશ્ચિત ઘટનાને અનુરૂપ હોય છે, તેથી સુનિશ્ચિત ઘટનાઓની સંખ્યા બરાબર છે જ્યાં ગતિશીલ ઢગલામાં ગાંઠોની સંખ્યા છે. આમ, ગતિશીલ ઢગલાઓ સઘન હોય છે. કાર્યક્ષમતાનું વિશ્લેષણ સામાન્ય કિસ્સામાં ગતિશીલ ઢગલાની કાર્યક્ષમતા મોટે ભાગે અજ્ઞાત છે. જો કે, પ્રાથમિકતાઓની એફાઇન ગતિના વિશેષ કિસ્સામાં, ગતિશીલ ઢગલાઓ ખૂબ જ કાર્યક્ષમ હોવાનું જાણીતું છે. એફાઇન ગતિ, કોઈ નિવેશ અથવા કાઢી નાંખવું નહીં આ ખાસ કિસ્સામાં, ગતિશીલ ઢગલા દ્વારા પ્રક્રિયા કરવામાં આવતી ઘટનાઓની મહત્તમ સંખ્યા ઢગલાના વૃક્ષ માળખાના સંક્રમક બંધમાં ધારની બરાબર સંખ્યા તરીકે દર્શાવી શકાય છે, જે ઊંચાઈના વૃક્ષ માટે છે. જો ખાલી શરૂ થતા ગતિશીલ ઢગલા પર નિવેશ અને કાઢી નાખવામાં આવે, તો પ્રક્રિયા કરવામાં આવતી ઘટનાઓની મહત્તમ સંખ્યા છે જો કે, આ બાઉન્ડ ચુસ્ત હોવાનું માનવામાં આવતું નથી, અને એકમાત્ર જાણીતી નીચલી બાઉન્ડ છે. પ્રકારો આ લેખ ઉપર વર્ણવ્યા મુજબ "સરળ" ગતિશીલ ઢગલાઓ સાથે વ્યવહાર કરે છે, પરંતુ અન્ય પ્રકારો વિશિષ્ટ કાર્યક્રમો માટે વિકસાવવામાં આવ્યા છે, જેમ કેઃ ફિબોનાકી ગતિશીલ ઢગલા વૃદ્ધિશીલ ગતિશીલ ઢગલા અન્ય ઢગલા જેવા ગતિશીલ અગ્રતા કતારો છેઃ ગતિશીલ હીટર ગતિજ લટકનાર સંદર્ભો ગતિજ ડેટા સ્ટ્રક્ચર્સ ઢગલાઓ (ડેટા સ્ટ્રક્ચર્સ)