ஒரு குவியல் 'பகுதி வரிசைப்படுத்தப்பட்டது' என்று குறிப்பிடப்படுகிறது மற்றும் 'பகுதி வரிசைப்படுத்தப்பட்டது' அல்ல. 'வரிசைப்படுத்து' என்ற வார்த்தைக்கு முழுமையான வரிசைப்படுத்துதல் (முழுமையான வரிசைப்படுத்துதல்) என்று பொருள். ஒரு குவியல் தன்னிச்சையாக ஓரளவுக்கு ஆர்டர் செய்யப்படவில்லை. கீழே காட்டப்பட்டுள்ளபடி, ஒரு குவியல் ஒரு அளவுகோலை (முறை) பின்பற்றி ஓரளவு வரிசைப்படுத்தப்படுகிறது.
எனவே, ஹீப்சார்ட் இரண்டு நிலைகளைக் கொண்டுள்ளது: குவியலை உருவாக்குதல் மற்றும் குவியல் மேல் இருந்து வரிசைப்படுத்தப்பட்ட உறுப்பை பிரித்தெடுத்தல். இரண்டாவது கட்டத்தில், ஒவ்வொரு பிரித்தெடுத்த பிறகு, குவியல் மீண்டும் கட்டப்பட்டது. ஒவ்வொரு மறுகட்டமைப்பும் அசல் கட்டிட செயல்முறையை விட வேகமானது, ஏனெனில் ஒரு உறுப்பு அகற்றப்பட்ட முந்தைய கட்டமைப்பிலிருந்து மறுகட்டமைப்பு செய்யப்படுகிறது. அதனுடன், heapsort முற்றிலும் வரிசைப்படுத்தப்படாத பட்டியலை வரிசைப்படுத்துகிறது.
இந்தக் கட்டுரையின் நோக்கம், குவியல்களை சுருக்கமாக விளக்கி, அதன் நேர சிக்கலை உருவாக்குவது (கீழே உள்ள நேர சிக்கலின் பொருளைப் பார்க்கவும்). இறுதியில், குறியீட்டு முறை C++ இல் செய்யப்படுகிறது.
குறைந்தபட்ச குவியல்
ஒரு குவியல் குறைந்தபட்ச குவியல் அல்லது அதிகபட்ச குவியலாக இருக்கலாம். அதிகபட்ச-குவியல் என்பது முதல் உறுப்பு மிக உயர்ந்த உறுப்பு ஆகும், மேலும் முழு மரமும் அல்லது தொடர்புடைய பட்டியலும் இறங்கு வரிசையில் ஓரளவு வரிசைப்படுத்தப்படும். ஒரு min-heap என்பது முதல் உறுப்பு குறைந்தபட்ச உறுப்பு ஆகும், மேலும் முழுப் பட்டியலும் ஏறுவரிசையில் ஓரளவு வரிசைப்படுத்தப்படும். இந்த கட்டுரையில், குறைந்தபட்ச குவியல் மட்டுமே கருதப்படுகிறது. குறிப்பு: குவியலின் தலைப்பில், ஒரு உறுப்பு முனை என்றும் அழைக்கப்படுகிறது.
ஒரு குவியல் ஒரு முழுமையான பைனரி மரம். பைனரி மரத்தை ஒரு வரிசையாக (பட்டியல்) வெளிப்படுத்தலாம்; மேலிருந்து கீழாகவும் இடமிருந்து வலமாகவும் படிக்கவும். ஒரு min-heap க்கான குவியல் சொத்து என்பது ஒரு பெற்றோர் முனை அதன் இரண்டு குழந்தைகளில் ஒவ்வொருவருக்கும் குறைவாகவோ அல்லது சமமாகவோ உள்ளது. வரிசைப்படுத்தப்படாத பட்டியலின் எடுத்துக்காட்டு:
| 9 | 19 | 24 | 5 | 3 | பதினொரு | 14 | 22 | 7 | 6 | 17 | பதினைந்து | ஏதுமில்லை | ஏதுமில்லை | ஏதுமில்லை |
| 0 | 1 | இரண்டு | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | பதினொரு | 12 | 13 | 14 |
இந்த அட்டவணையின் முதல் வரிசை வரிசையின் கூறுகள் ஆகும். இரண்டாவது வரிசையில் பூஜ்ஜிய அடிப்படையிலான குறியீடுகள் உள்ளன. இந்த உறுப்புகளின் பட்டியலை ஒரு மரமாக வெளிப்படுத்தலாம். முழு பைனரி மரத்தை உருவாக்க பூஜ்ய கூறுகள் சேர்க்கப்பட்டுள்ளன. கண்டிப்பாகச் சொன்னால், பூஜ்ய கூறுகள் பட்டியலில் (மரம்) பகுதியாக இல்லை. இந்த பட்டியலில் எந்த வரிசையும் இல்லை, எனவே இது இன்னும் குவியலாக இல்லை. குவியல் சொத்தின்படி, பகுதியளவு வரிசைப்படுத்தும் போது அது ஒரு குவியலாக மாறும்.
முனைகளுக்கும் குறியீடுகளுக்கும் இடையிலான உறவு
குவியல் என்பது ஒரு முழுமையான பைனரி மரமாகும் என்பதை நினைவில் கொள்ளுங்கள், குவியல் உள்ளமைவு (குவியல் சொத்து). முந்தைய பட்டியல் இன்னும் குவியலாக இல்லை, ஏனெனில் கூறுகள் குவியல் பண்புக்குக் கீழ்ப்படியவில்லை. min-heap பண்புக்கு ஏற்ப உறுப்புகளை பகுதி வரிசையில் மறுசீரமைத்த பிறகு இது ஒரு குவியலாக மாறும். பகுதி வரிசையை பகுதி வரிசையாகக் காணலாம் ('வரிசை' என்ற வார்த்தைக்கு முழுமையான வரிசைப்படுத்தல் என்று பொருள்).
பைனரி மரம் ஒரு குவியலாக இருந்தாலும் இல்லாவிட்டாலும், ஒவ்வொரு பெற்றோருக்கும் இலை (கடைசி) முனைகளைத் தவிர இரண்டு குழந்தைகள் உள்ளனர். ஒவ்வொரு பெற்றோருக்கும் அதன் குழந்தைகளுக்கும் இடையே உள்ள குறியீடுகளுக்கு இடையே ஒரு கணித உறவு உள்ளது. இது பின்வருமாறு: பெற்றோர் குறியீட்டு i இல் இருந்தால், இடது குழந்தை குறியீட்டில் உள்ளது:
இரண்டு * நான் + 1மற்றும் சரியான குழந்தை குறியீட்டில் உள்ளது:
இரண்டு * நான் + இரண்டுஇது பூஜ்ஜிய அடிப்படையிலான அட்டவணைப்படுத்தலுக்கானது. எனவே, குறியீட்டு 0 இல் உள்ள பெற்றோரின் இடது குழந்தை குறியீட்டு 2×0+1=1 மற்றும் வலது குழந்தை 2×0+2=2. குறியீட்டு 1 இல் ஒரு பெற்றோர் அதன் இடது குழந்தை குறியீட்டு 2×1+1=3 மற்றும் வலது குழந்தை குறியீட்டு 2×1+2=4; மற்றும் பல.
மினி-ஹீப் சொத்தின்படி, i இல் உள்ள பெற்றோர் 2i+1 இல் இடது குழந்தைக்கு குறைவாகவோ அல்லது சமமாகவோ, 2i+2 இல் வலது குழந்தைக்கு குறைவாகவோ அல்லது சமமாகவோ இருக்கிறார்.
குவியல்
குவித்தல் என்றால் குவியல் கட்டுதல். இது ஒரு பட்டியலின் (அல்லது தொடர்புடைய மரம்) கூறுகளை மறுசீரமைப்பதாகும், இதனால் அவை குவியல் பண்புகளை திருப்திப்படுத்துகின்றன. பெருக்குதல் செயல்முறையின் முடிவில், பட்டியல் அல்லது மரம் ஒரு குவியல்.
முந்தைய வரிசைப்படுத்தப்படாத பட்டியல் குவிக்கப்பட்டால், அது:
| 3 | 5 | பதினொரு | 7 | 6 | பதினைந்து | 14 | 22 | 9 | 19 | 17 | 24 | ஏதுமில்லை | ஏதுமில்லை | ஏதுமில்லை |
| 0 | 1 | இரண்டு | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | பதினொரு | 12 | 13 | 14 |
குறிப்பு: பட்டியலில் 15 இல்லை, 12 கூறுகள் உள்ளன. இரண்டாவது வரிசையில் குறியீடுகள் உள்ளன. குவியல் கட்டும் செயல்பாட்டில், கூறுகள் சரிபார்க்கப்பட வேண்டும், மேலும் சில மாற்றப்பட்டன.
சிறிய மற்றும் முதல் உறுப்பு 3. மீதமுள்ள உறுப்புகள் ஏறுவரிசையில் ஆனால் அலை அலையான முறையில் பின்பற்றப்படுகின்றன. 2i+1 மற்றும் 2i+2 நிலைகளில் உள்ள இடது மற்றும் வலது குழந்தைகள் ஒவ்வொருவரும் i இல் உள்ள பெற்றோரை விட அதிகமாகவோ அல்லது சமமாகவோ இருந்தால், இது min-heap ஆகும். இது முழு வரிசைப்படுத்தல் அல்லது வரிசைப்படுத்துதல் அல்ல. குவியல் சொத்தின் படி இது பகுதி வரிசைப்படுத்தல் ஆகும். இங்கிருந்துதான் குவியல் வரிசைக்கான அடுத்த கட்டம் தொடங்குகிறது.
Heapify நேர சிக்கலானது
நேர சிக்கலானது என்பது சில குறியீட்டின் தொடர்புடைய இயக்க நேரமாகும். அந்த குறியீட்டை முடிக்க முக்கிய செயல்பாடுகளின் எண்ணிக்கையாக இது பார்க்கப்படுகிறது. குவியல் கட்டிடத்திற்கு வெவ்வேறு வழிமுறைகள் உள்ளன. மிகவும் திறமையான மற்றும் வேகமானவை தொடர்ந்து பட்டியலை இரண்டாகப் பிரித்து, கீழே இருந்து உறுப்புகளைச் சரிபார்த்து, பின்னர் சில உறுப்புகளை மாற்றும். பட்டியலில் உள்ள நடைமுறை கூறுகளின் எண்ணிக்கையை N ஆக இருக்கட்டும். இந்த அல்காரிதம் மூலம், முக்கிய செயல்பாடுகளின் அதிகபட்ச எண்ணிக்கை (இடமாற்றம்) N ஆகும். ஹீப்பிஃபிங்கிற்கான நேர சிக்கலானது முன்பு இவ்வாறு கொடுக்கப்பட்டது:
ஓ ( n )n என்பது N மற்றும் முக்கிய செயல்பாடுகளின் அதிகபட்ச சாத்தியமான எண்ணிக்கையாகும். இந்த குறியீடானது பிக்-ஓ குறிமுறை என்று அழைக்கப்படுகிறது. இது O உடன் பெரிய எழுத்தில் தொடங்குகிறது, அதைத் தொடர்ந்து அடைப்புக்குறிக்குள். அடைப்புக்குறிக்குள் அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகளுக்கான வெளிப்பாடு ஆகும்.
நினைவில் கொள்ளுங்கள்: சேர்க்கப்படும் அதே விஷயம் மீண்டும் மீண்டும் தொடர்ந்தால் கூட்டல் பெருக்கல் ஆகலாம்.
ஹீப்சார்ட் விளக்கம்
வரிசைப்படுத்தப்படாத முந்தைய பட்டியல் குவியல்களை விளக்குவதற்குப் பயன்படுத்தப்படும். கொடுக்கப்பட்ட பட்டியல்:
9 19 24 5 3 பதினொரு 14 22 7 6 17 பதினைந்துபட்டியலிலிருந்து தயாரிக்கப்பட்ட மினி-குவியல்:
3 5 பதினொரு 7 6 பதினைந்து 14 22 9 19 17 24ஹீப்சார்ட்டின் முதல் கட்டம், உற்பத்தி செய்யப்பட்ட குவியல்களை உற்பத்தி செய்வதாகும். இது ஓரளவு வரிசைப்படுத்தப்பட்ட பட்டியல். இது வரிசைப்படுத்தப்பட்ட (முற்றிலும் வரிசைப்படுத்தப்பட்ட) பட்டியல் அல்ல.
இரண்டாவது கட்டத்தில், குவியல் குவியலில் இருந்து முதல் உறுப்பாக இருக்கும் குறைந்தபட்ச உறுப்பை அகற்றுவது, மீதமுள்ள குவியலை மீண்டும் குவிப்பது மற்றும் முடிவுகளில் உள்ள குறைந்தபட்ச உறுப்புகளை அகற்றுவது ஆகியவை அடங்கும். குறைந்த உறுப்பு எப்பொழுதும் ரீ-ஹீப்பிஃபை செய்யப்பட்ட குவியலில் முதல் உறுப்பு ஆகும். உறுப்புகள் அகற்றப்பட்டு தூக்கி எறியப்படுவதில்லை. அவை அகற்றப்படும் வரிசையில் வேறு ஒரு அணிக்கு அனுப்பப்படலாம்.
இறுதியில், புதிய அணிவரிசை அனைத்து உறுப்புகளையும் ஏறுவரிசையில் (முழுமையாக) வரிசைப்படுத்தியிருக்கும்; மேலும் இனி ஓரளவுக்கு மட்டும் ஆர்டர் செய்யப்படவில்லை.
இரண்டாவது கட்டத்தில், முதலில் செய்ய வேண்டியது 3 ஐ அகற்றி புதிய வரிசையில் வைக்க வேண்டும். முடிவுகள்:
3மற்றும்
5 பதினொரு 7 6 பதினைந்து 14 22 9 19 17 24முதல் உறுப்பு பிரித்தெடுக்கப்படுவதற்கு முன்பு மீதமுள்ள உறுப்புகள் குவிக்கப்பட வேண்டும். மீதமுள்ள உறுப்புகளின் குவியல் ஆகலாம்:
5 6 7 9 பதினைந்து 14 22 பதினொரு 19 17 245ஐ பிரித்தெடுத்து புதிய பட்டியலில் (வரிசை) சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5மற்றும்
6 7 9 பதினைந்து 14 22 பதினொரு 19 17 24மீதமுள்ள தொகுப்பை அதிகப்படுத்துவது:
6 7 9 பதினைந்து 14 22 பதினொரு 19 17 246ஐ பிரித்தெடுத்து புதிய பட்டியலில் (வரிசை) சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6மற்றும்
7 9 பதினைந்து 14 22 பதினொரு 19 17 24மீதமுள்ள தொகுப்பை அதிகப்படுத்துவது:
7 9 பதினொரு 14 22 பதினைந்து 19 17 247ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6 7மற்றும்
9 பதினொரு 14 22 பதினைந்து 19 17 24மீதமுள்ள தொகுப்பை பெருக்குவது:
9 பதினொரு 14 22 பதினைந்து 19 17 249ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால், முடிவுகள் கிடைக்கும்:
3 5 6 7 9மற்றும்
பதினொரு 14 22 பதினைந்து 19 17 24மீதமுள்ள தொகுப்பை பெருக்குவது:
பதினொரு 14 17 பதினைந்து 19 22 2411ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6 7 9 பதினொருமற்றும்
14 17 பதினைந்து 19 22 24மீதமுள்ள தொகுப்பை அதிகப்படுத்துவது:
14 17 பதினைந்து 19 22 2414ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6 7 9 பதினொரு 14மற்றும்
17 பதினைந்து 19 22 24மீதமுள்ள தொகுப்பை அதிகப்படுத்துவது:
பதினைந்து 17 19 22 2415ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6 7 9 பதினொரு 14 பதினைந்துமற்றும்
17 19 22 24மீதமுள்ள தொகுப்பை அதிகப்படுத்துவது:
17 19 22 2417ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6 7 9 பதினொரு 14 பதினைந்து 17மற்றும்
19 22 24மீதமுள்ள தொகுப்பை அதிகப்படுத்துவது:
19 22 2419ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6 7 9 பதினொரு 14 பதினைந்து 17 19மற்றும்
22 24மீதமுள்ள தொகுப்பை பெருக்குவது:
22 2422ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6 7 9 பதினொரு 14 பதினைந்து 17 19 22மற்றும்
24மீதமுள்ள தொகுப்பை பெருக்குவது:
2424ஐ பிரித்தெடுத்து புதிய பட்டியலில் சேர்த்தால் முடிவுகள் கிடைக்கும்:
3 5 6 7 9 பதினொரு 14 பதினைந்து 17 19 22 24மற்றும்
- - -குவியல் வரிசை இப்போது காலியாக உள்ளது. தொடக்கத்தில் இருந்த அனைத்து கூறுகளும் இப்போது புதிய வரிசையில் (பட்டியலில்) மற்றும் வரிசைப்படுத்தப்பட்டுள்ளன.
ஹீப்சார்ட் அல்காரிதம்
ஹீப்சார்ட் இரண்டு நிலைகளைக் கொண்டுள்ளது என்பதை வாசகர் பாடப்புத்தகங்களில் படித்திருக்கலாம் என்றாலும், ஹீப்சார்ட் ஒரு கட்டத்தைக் கொண்டிருப்பதைக் காணலாம், இது கொடுக்கப்பட்ட வரிசையை மீண்டும் மீண்டும் சுருக்குகிறது. அதனுடன், ஹீப்சார்ட் மூலம் வரிசைப்படுத்துவதற்கான வழிமுறை பின்வருமாறு:
- வரிசைப்படுத்தப்படாத பட்டியலைக் குவிக்கவும்.
- குவியலின் முதல் உறுப்பைப் பிரித்தெடுத்து புதிய பட்டியலின் முதல் உறுப்பாக வைக்கவும்.
- மீதமுள்ள பட்டியலைக் குவிக்கவும்.
- புதிய குவியலின் முதல் உறுப்பைப் பிரித்தெடுத்து, புதிய பட்டியலின் அடுத்த உறுப்பாக வைக்கவும்.
- குவியல் பட்டியல் காலியாகும் வரை முந்தைய படிகளை மீண்டும் செய்யவும். இறுதியில், புதிய பட்டியல் வரிசைப்படுத்தப்படுகிறது.
ஹீப்சார்ட் நேரம் சிக்கலானது சரியானது
ஹீப்சார்ட்டின் நேர சிக்கலைத் தீர்மானிக்க ஒரு-நிலை அணுகுமுறை பயன்படுத்தப்படுகிறது. வரிசைப்படுத்தப்படாத 8 கூறுகள் உள்ளன என்று வைத்துக்கொள்வோம்.
அதிகப்படுத்துவதற்கான சாத்தியமான அதிகபட்ச செயல்பாடுகள் 8 கூறுகள் ஆகும் 8 .தி மீதமுள்ளவற்றைக் குவிக்க அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகள் 7 கூறுகள் ஆகும் 7 .
தி மீதமுள்ளவற்றைக் குவிக்க அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகள் 6 கூறுகள் ஆகும் 6 .
தி மீதமுள்ளவற்றைக் குவிக்க அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகள் 5 கூறுகள் ஆகும் 5 .
தி மீதமுள்ளவற்றைக் குவிக்க அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகள் 4 கூறுகள் ஆகும் 4 .
தி மீதமுள்ளவற்றைக் குவிக்க அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகள் 3 கூறுகள் ஆகும் 3 .
தி மீதமுள்ளவற்றைக் குவிக்க அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகள் இரண்டு கூறுகள் ஆகும் இரண்டு .
தி மீதமுள்ளவற்றைக் குவிக்க அதிகபட்ச எண்ணிக்கையிலான செயல்பாடுகள் 1 உறுப்பு ஆகும் 1 .
சாத்தியமான அதிகபட்ச செயல்பாடுகள்:
8 + 7 + 6 + 5 + 4 + 3 + இரண்டு + 1 = 36இந்த எண்ணிக்கையிலான செயல்பாடுகளின் சராசரி:
36 / 8 = 4.5முதல் உறுப்பு அகற்றப்பட்டபோது, முந்தைய விளக்கப்படத்தில் கடைசி நான்கு குவியல்கள் மாறவில்லை என்பதைக் கவனியுங்கள். முதல் உறுப்பு அகற்றப்பட்டபோது முந்தைய சில குவியல்களும் மாறவில்லை. அதனுடன், முக்கிய செயல்பாடுகளின் சிறந்த சராசரி எண்ணிக்கை (மாற்றங்கள்) 3 மற்றும் 4.5 அல்ல. எனவே, முக்கிய செயல்பாடுகளின் சிறந்த மொத்த சராசரி எண்ணிக்கை:
24 = 8 எக்ஸ் 3=> 24 = 8 எக்ஸ் பதிவு < துணை > இரண்டு < / துணை > 8
பதிவு முதல் இரண்டு 8 = 3.
பொதுவாக, ஹீப்சார்ட்டின் சராசரி வழக்கு நேர சிக்கலானது:
ஓ ( n log2n )புள்ளி என்பது பெருக்கல் மற்றும் n என்பது N, பட்டியலில் உள்ள உறுப்புகளின் மொத்த எண்ணிக்கை (பட்டியல்).
முதல் உறுப்பை பிரித்தெடுக்கும் செயல்பாடு புறக்கணிக்கப்பட்டது என்பதை நினைவில் கொள்ளவும். நேர சிக்கலானது என்ற தலைப்பில், ஒப்பீட்டளவில் குறுகிய நேரத்தை எடுக்கும் செயல்பாடுகள் புறக்கணிக்கப்படுகின்றன.
C++ இல் குறியீட்டு முறை
C++ இன் அல்காரிதம் லைப்ரரியில், make_heap() செயல்பாடு உள்ளது. தொடரியல்:
டெம்ப்ளேட் < வர்க்கம் RandomAccessIterator, வர்க்கம் ஒப்பிடு >constexpr வெற்றிடமானது செய்ய_குவியல் ( முதலில் RandomAccessIterator, கடைசியாக RandomAccessIterator, Compare comp ) ;
ஒரு திசையனின் முதல் உறுப்பை அதன் முதல் வாதமாகவும், அதன் கடைசி வாதமாகத் திசையன் முனைக்கு அப்பால் சுட்டிக் காட்டும் இடிரேட்டரையும் இது எடுத்துக்கொள்கிறது. முந்தைய வரிசைப்படுத்தப்படாத பட்டியலுக்கு, குறைந்தபட்ச குவியலைப் பெற, தொடரியல் பின்வருமாறு பயன்படுத்தப்படும்:
திசையன் < முழு எண்ணாக > vtr = { 9 , 19 , 24 , 5 , 3 , பதினொரு , 14 , 22 , 7 , 6 , 17 , பதினைந்து } ;திசையன் < முழு எண்ணாக > :: மீண்டும் செய்பவர் iterB = vtr தொடங்கும் ( ) ;
திசையன் < முழு எண்ணாக > :: மீண்டும் செய்பவர் iterE = vtr முடிவு ( ) ;
செய்ய_குவியல் ( iterB, iterE, பெரியது < முழு எண்ணாக > ( ) ) ;
இந்தக் குறியீடு வெக்டார் உள்ளடக்கத்தை குறைந்தபட்ச குவியல் உள்ளமைவாக மாற்றுகிறது. பின்வரும் C++ வெக்டர்களில், இரண்டு வரிசைகளுக்குப் பதிலாக இரண்டு திசையன்கள் பயன்படுத்தப்படும்.
வெக்டரின் முதல் உறுப்பை நகலெடுத்து திருப்பி அனுப்ப, திசையன் தொடரியல் பயன்படுத்தவும்:
constexpr குறிப்பு முன் ( ) ;வெக்டரின் முதல் உறுப்பை அகற்றி அதை தூக்கி எறிய, திசையன் தொடரியல் பயன்படுத்தவும்:
constexpr மறு செய்கை அழித்தல் ( const_iterator நிலை )வெக்டரின் பின்புறத்தில் (அடுத்த உறுப்பு) ஒரு உறுப்பைச் சேர்க்க, திசையன் தொடரியல் பயன்படுத்தவும்:
constexpr வெற்றிடமானது பின்னால் தள்ளு ( நிலையான டி & எக்ஸ் ) ;திட்டத்தின் ஆரம்பம்:
##
#
பயன்படுத்தி பெயர்வெளி வகுப்பு ;
அல்காரிதம் மற்றும் வெக்டர் நூலகங்கள் சேர்க்கப்பட்டுள்ளன. நிரலில் அடுத்தது heapsort() செயல்பாடு, இது:
வெற்றிடமானது குவியல் ( திசையன் < முழு எண்ணாக > & oldV, திசையன் < முழு எண்ணாக > & புதிய வி ) {என்றால் ( பழைய வி. அளவு ( ) > 0 ) {
திசையன் < முழு எண்ணாக > :: மீண்டும் செய்பவர் iterB = பழைய வி. தொடங்கும் ( ) ;
திசையன் < முழு எண்ணாக > :: மீண்டும் செய்பவர் iterE = பழைய வி. முடிவு ( ) ;
செய்ய_குவியல் ( iterB, iterE, பெரியது < முழு எண்ணாக > ( ) ) ;
முழு எண்ணாக அடுத்தது = பழைய வி. முன் ( ) ;
பழைய வி. அழிக்க ( iterB ) ;
புதிய வி. பின்னால் தள்ளு ( அடுத்தது ) ;
குவியல் ( பழைய வி, புதிய வி ) ;
}
}
இது ஒரு சுழல்நிலை செயல்பாடு. இது C++ அல்காரிதம் லைப்ரரியின் make_heap() செயல்பாட்டைப் பயன்படுத்துகிறது. செயல்பாட்டு வரையறையில் உள்ள இரண்டாவது குறியீடு பிரிவு, குவியல் கட்டிடத்திற்குப் பிறகு பழைய திசையனிலிருந்து முதல் உறுப்பைப் பிரித்தெடுத்து, புதிய திசையனுக்கான அடுத்த உறுப்பாக சேர்க்கிறது. செயல்பாடு வரையறையில், திசையன் அளவுருக்கள் குறிப்புகளாகும், அதே நேரத்தில் செயல்பாடு அடையாளங்காட்டிகளுடன் (பெயர்கள்) அழைக்கப்படுகிறது.
இதற்கு பொருத்தமான C++ முக்கிய செயல்பாடு:
முழு எண்ணாக முக்கிய ( முழு எண்ணாக argc, கரி ** argv ){
திசையன் < முழு எண்ணாக > பழைய வி = { 9 , 19 , 24 , 5 , 3 , பதினொரு , 14 , 22 , 7 , 6 , 17 , பதினைந்து } ;
திசையன் < முழு எண்ணாக > புதிய வி ;
குவியல் ( பழைய வி, புதிய வி ) ;
க்கான ( முழு எண்ணாக நான் = 0 ; நான் < புதிய வி. அளவு ( ) ; நான் ++ ) {
கூட் << புதிய வி [ நான் ] << '''' ;
}
கூட் << endl ;
திரும்ப 0 ;
}
வெளியீடு:
3 5 6 7 9 பதினொரு 14 பதினைந்து 17 19 22 24வரிசைப்படுத்தப்பட்டது (முற்றிலும்).
முடிவுரை
பொதுவாக ஹீப்சார்ட் என அழைக்கப்படும் ஹீப் வரிசையின் தன்மை மற்றும் செயல்பாடு பற்றி கட்டுரை விரிவாக விவாதிக்கப்பட்டது. Heapify Time Complexity, Heapsort விளக்கப்படம் மற்றும் Heapsort ஒரு அல்காரிதம் ஆகியவை எடுத்துக்காட்டுகளால் மூடப்பட்டு ஆதரிக்கப்படுகின்றன. நன்கு எழுதப்பட்ட ஹீப்சார்ட் நிரலுக்கான சராசரி நேர சிக்கலானது O(nlog(n))