Queap
கணினி அறிவியலில், ஒரு க்யூப் என்பது முன்னுரிமை வரிசை தரவு கட்டமைப்பாகும். தரவு அமைப்பு தன்னிச்சையான கூறுகளை செருகவும் நீக்கவும் அனுமதிக்கிறது, அதே போல் மிக உயர்ந்த முன்னுரிமை உறுப்பை மீட்டெடுக்கவும் அனுமதிக்கிறது. ஒவ்வொரு நீக்குதலும் அகற்றப்பட்ட உருப்படியை விட நீண்ட காலமாக கட்டமைப்பில் இருந்த உருப்படிகளின் எண்ணிக்கையில் கடனுதவி செய்யப்பட்ட நேர மடக்கை எடுக்கும். செருகல்கள் நிலையான கடனுதவி நேரத்தை எடுக்கும். தரவு அமைப்பு இரட்டிப்பாக இணைக்கப்பட்ட பட்டியல் மற்றும் 2-4 மர தரவு கட்டமைப்பைக் கொண்டுள்ளது, ஒவ்வொன்றும் அதன் குறைந்தபட்ச முன்னுரிமை உறுப்பைக் கண்காணிக்க மாற்றியமைக்கப்பட்டுள்ளன. இரண்டு மடங்கு இணைக்கப்பட்ட பட்டியலில் புதிதாக செருகப்பட்ட கூறுகளை வைத்திருப்பது கட்டமைப்பின் அடிப்படை செயல்பாடாகும், ஒரு நீக்குதல் பட்டியல் உருப்படிகளில் ஒன்றை அகற்றும் வரை, அவை அனைத்தும் 2 முதல் 4 மரத்திற்குள் நகர்த்தப்படுகின்றன. 2-4 மரம் அதன் கூறுகளை வழக்கமான முன்னுரிமை-வரிசைப்படுத்தப்பட்ட வரிசையை விட செருகும் வரிசையில் சேமிக்கிறது. தரவு அமைப்பு மற்றும் அதன் பெயர் இரண்டும் ஜான் ஐகோனோ மற்றும் ஸ்டீபன் லாங்கர்மேன் ஆகியோரால் வடிவமைக்கப்பட்டன. ஒரு வரிசை என்பது ஒரு முன்னுரிமை வரிசையாகும், இது O (1) கடன்தொகை நேரத்தில் கூறுகளைச் செருகுகிறது, மேலும் பெறப்பட வேண்டிய உறுப்பை விட நீண்ட காலமாக குவியலில் இருந்த k உருப்படிகள் இருந்தால் O (பதிவு (k + 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 இல் உள்ளது (பிட் மாறி அமைக்கப்பட்டுள்ளதா என்பதைச் சரிபார்ப்பதன் மூலம் செய்யப்படுகிறது). பட்டியல் எல் இல் சேமிக்கப்பட்டுள்ள அனைத்து உறுப்புகளும் பின்னர் 2-4 மரத்தில் சேர்க்கப்பட்டு, ஒவ்வொரு உறுப்பின் பிட் மாறியை பூஜ்ஜியமாக அமைக்கின்றன. ஒரு வரிசை 2 முதல் 4 மர அமைப்பு பண்புகளை மட்டுமே பயன்படுத்துகிறது, தேடல் மரம் அல்ல. மாற்றியமைக்கப்பட்ட 2 முதல் 4 மரங்களின் அமைப்பு பின்வருமாறு. பட்டியல் எல் பின்வரும் கூறுகளின் தொகுப்பைக் கொண்டுள்ளது என்று வைத்துக்கொள்வோம்ஃ நீக்குதல் செயல்பாடு செயல்படுத்தப்படும்போது, எல் இல் சேமிக்கப்பட்டுள்ள உறுப்புகளின் தொகுப்பு அந்த வரிசையில் 2 முதல் 4 மரத்தின் இலைகளில் சேர்க்கப்பட்டு, எல்லையற்ற விசையைக் கொண்ட ஒரு போலி இலை மூலம் தொடரப்படுகிறது. T இன் ஒவ்வொரு உள் முனையிலும் ஒரு சுட்டிக்காட்டி உள்ளது, இது சப்ட்ரீ v இல் உள்ள மிகச்சிறிய உருப்படியை சுட்டிக்காட்டுகிறது. பாதை P இல் உள்ள ஒவ்வொரு உள் முனையிலும் ஒரு சுட்டிக்காட்டி உள்ளது, இது மிகச்சிறிய விசையை சுட்டிக்காட்டுகிறது. P பாதையில் உள்ள ஒவ்வொரு உள் முனையின் சுட்டிகளும் புறக்கணிக்கப்படுகின்றன. வரிசைக்கு ஒரு சுட்டிக்காட்டி உள்ளது, இது டி இல் உள்ள மிகச்சிறிய உறுப்பை சுட்டிக்காட்டுகிறது. வரிசை பயன்பாட்டில் உயர் முன்னுரிமை நிகழ்வுகளின் தனித்துவமான தொகுப்பு மற்றும் செயலாக்கத்திற்கான மிக உயர்ந்த முன்னுரிமை நிகழ்வைப் பிரித்தெடுப்பது ஆகியவை அடங்கும். செயல்பாடுகள் இரட்டை இணைக்கப்பட்ட பட்டியல் எல் இல் குறைந்தபட்ச உறுப்பை சுட்டிக்காட்டும் ஒரு சுட்டியாக மினல் இருக்கட்டும், 2 முதல் 4 மரத்தில் சேமிக்கப்பட்ட குறைந்தபட்ச உறுப்பாக இருக்க வேண்டும், டி, கே டி இல் சேமிக்கப்பட்ட உறுப்புகளின் எண்ணிக்கையாக இருக்க வேண்டும், மற்றும் n க்யூப் க்யூவில் சேமிக்கப்பட்ட உறுப்புகளின் மொத்த எண்ணிக்கையாக இருக்க வேண்டும். செயல்பாடுகள் பின்வருமாறுஃ புதிய (கேள்வி): ஒரு புதிய வெற்று வரிசையை துவக்குகிறது. வெற்று இரு மடங்கு இணைக்கப்பட்ட பட்டியல் L மற்றும் 2-4 மரம் T ஐ துவக்கவும். k மற்றும் n ஐ பூஜ்ஜியமாக அமைக்கவும். செருகவும் (Q, x): க்யூப் செய்ய x உறுப்பைச் சேர்க்கவும். எல் பட்டியலில் x உறுப்பைச் செருகவும். எல் பட்டியலில் உறுப்பு இருப்பதை நிரூபிக்க x உறுப்பில் உள்ள பிட்டை ஒன்றுக்கு அமைக்கவும். பட்டியலில் x மிகச்சிறிய உறுப்பு என்றால் மினல் சுட்டிக்காட்டியைப் புதுப்பிக்கவும். n ஐ 1 ஆல் அதிகரிக்கவும். குறைந்தபட்சம் (கியூ): க்யூப் கியூவிலிருந்து மிகச்சிறிய உறுப்புக்கு ஒரு சுட்டியை மீட்டமைக்கவும். விசை (மினல்) <விசை () என்றால், மினல் திரும்பவும். இல்லையெனில் திரும்பிச் செல்லுங்கள். நீக்கவும் (க்யூ, எக்ஸ்): க்யூப் க்யூவிலிருந்து உறுப்பு x ஐ அகற்றவும். உறுப்பு x இன் பிட் ஒன்றுக்கு அமைக்கப்பட்டிருந்தால், உறுப்பு எல் பட்டியலில் சேமிக்கப்படும். எல் முதல் டி வரை அனைத்து உறுப்புகளையும் சேர்த்து, ஒவ்வொரு உறுப்பின் பிட்டையும் பூஜ்ஜியமாக அமைக்கவும். ஒவ்வொரு உறுப்பும் 2 முதல் 4 மரத்தின் செருகும் செயல்பாட்டைப் பயன்படுத்தி டி இன் வலது பெரும்பாலான குழந்தையின் பெற்றோரிடம் சேர்க்கப்படுகிறது. எல் காலியாகிறது. குழந்தைகள் புதிய/மாற்றியமைக்கப்பட்ட அனைத்து முனைகளுக்கான சுட்டிகளையும் புதுப்பிக்கவும், பெற்றோர் மூலத்திற்கு சமமாக இருக்கும் வரை அடுத்த பெற்றோருடன் செயல்முறையை மீண்டும் செய்யவும். மூலத்திலிருந்து முனைக்கு நடந்து சென்று மதிப்புகளைப் புதுப்பிக்கவும். k ஐ n க்கு சமமாக அமைக்கவும். x தனிமத்தின் பிட் பூஜ்ஜியமாக அமைக்கப்பட்டால், x என்பது T இன் இலை. 2-4 மரம் நீக்கும் செயல்பாட்டைப் பயன்படுத்தி x ஐ நீக்கவும். முனை x இலிருந்து தொடங்கி, T இல் முனைக்கு நடந்து, புதுப்பித்தல் மற்றும் சுட்டிகள். n மற்றும் k ஐ 1 ஆல் குறைக்கவும். டெலிட்மின் (கியூ): க்யூப் கியூவிலிருந்து மிகச்சிறிய உறுப்பை நீக்கி திருப்பி விடுங்கள். குறைந்தபட்ச (கியூ) செயல்பாட்டை அழைக்கவும். செயல்பாடு மினிற்குத் திருப்பித் தருகிறது. நீக்குதல் (கேள்வி, நிமிடம்) செயல்பாட்டைத் தொடங்குங்கள். மினிற்குத் திரும்பு. கிளீன்அப் (கியூ): எல் மற்றும் ட்ரீ டி பட்டியலில் உள்ள அனைத்து உறுப்புகளையும் நீக்குங்கள். எல் பட்டியலில் உள்ள முதல் உறுப்பிலிருந்து தொடங்கி, ஒவ்வொரு முனையையும் நீக்கி, பட்டியலைக் கடந்து செல்லுங்கள். T மரத்தின் வேரிலிருந்து தொடங்கி, மரத்தில் உள்ள ஒவ்வொரு முனையையும் நீக்கி, போஸ்ட்-ஆர்டர் டிராவர்சல் வழிமுறையைப் பயன்படுத்தி மரத்தை கடந்து செல்லுங்கள். பகுப்பாய்வு அமோர்டைஸ் செய்யப்பட்ட பகுப்பாய்வைப் பயன்படுத்தி இயங்கும் நேரம் பகுப்பாய்வு செய்யப்படுகிறது. க்யூப் கியூ-க்கான சாத்தியமான செயல்பாடு எங்கே இருக்கும். செருகவும் (Q, x): செயல்பாட்டின் செலவு O (1) ஆகும். பட்டியல் எல்-இன் அளவு ஒன்று அதிகரித்து, ஆற்றல் சில நிலையான சி அதிகரிக்கிறது. குறைந்தபட்சம் (கியூ): செயல்பாடு தரவு கட்டமைப்பை மாற்றாது, எனவே கடன்தொகை செலவு அதன் உண்மையான செலவு, ஓ (1) க்கு சமமாக இருக்கும். நீக்குதல் (Q, x): இரண்டு நிகழ்வுகள் உள்ளன. வழக்கு 1 x மரம் T இல் இருந்தால், கடனுதவி செலவு மாற்றப்படாது. நீக்குதல் செயல்பாடு ஓ (1) கடனுதவி செய்யப்பட்ட 2-4 மரம் ஆகும். மரத்திலிருந்து x அகற்றப்பட்டதால், சுட்டிகள் புதுப்பிக்கப்பட வேண்டியிருக்கலாம். அதிகபட்சம், புதுப்பிப்புகள் இருக்கும். வழக்கு 2 x பட்டியல் L இல் இருந்தால், L இலிருந்து வரும் அனைத்து உறுப்புகளும் T இல் செருகப்படுகின்றன. சுட்டிகள் மற்றும் சுட்டிகளைச் சேர்த்து புதுப்பித்த பிறகு, செலவிடப்பட்ட மொத்த நேரம் வரையறுக்கப்பட்டுள்ளது. இரண்டாவது செயல்பாடு T இலிருந்து x ஐ நீக்குவது, மற்றும் x இலிருந்து x க்கு செல்லும் பாதையில் நடப்பது, சரிசெய்தல் மற்றும் மதிப்புகள். அதிகபட்சமாக நேரம் செலவிடப்படுகிறது. அப்படியானால், கடனுதவி செலவு இருக்கும். நீக்குதல் (கியூ, எக்ஸ்): குறைந்தபட்சம் (கியூ) மற்றும் நீக்குதல் (கியூ, எக்ஸ்) ஆகியவற்றின் கடனுதவி செய்யப்பட்ட செலவின் கூட்டல் ஆகும். குறியீடு எடுத்துக்காட்டு ஒரு க்யூப்பின் ஒரு சிறிய ஜாவா செயல்படுத்தல்ஃ பொது வகுப்பு க்யூப் {பொது int n, k; பொது பட்டியல் <உறுப்பு> l;// உறுப்பு என்பது ஒரு பொதுவான தரவு வகை. பொது குயாப்ட்ரீ டி;// ஒரு 2-4 மரம், குயாப் நோக்கத்திற்காக பொது உறுப்பு மின்லுக்காக மாற்றியமைக்கப்பட்டது; தனியார் குயாப் () {n = 0; k = 0; l = புதிய இணைக்கப்பட்ட பட்டியல் <உறுப்பு> (); t = புதிய குயாப்ட்ரீ ();} பொது நிலையான குயாப் புதிய () {புதிய குயாப் () ஐத் திருப்பவும்;} பொது நிலையான வெற்றிட செருகல் (குயாப் க்யூ, உறுப்பு x) {என்றால் (க்யூ. என் = = 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. விசை;} பொது நிலையான வெற்றிட நீக்குதல் (கியூயாப் கியூ, கியூயாப்நோட் x) {Q.t.deleteLeaf (x);-- கியூ. என்;-- கியூ. கே;} பொது நிலையான வெற்றிட நீக்குதல் (கியூயாப் கியூ, எலிமெண்ட் x) {கியூயாப் நோட் என்; (x.inList) {// பட்டியலில் உள்ள அனைத்து உறுப்புகளின் பட்டியலையும் பொய்யானால் n = Q.t.insertList (கியூ. எல், எக்ஸ்); கியூ. கே = கியூ. என்; நீக்குதல் (கியூ, என்);) இல்லையெனில் ((என் = Q.t.x0.cv).