ఒక కుప్పను 'పాక్షికంగా ఆర్డర్'గా సూచిస్తారు మరియు 'పాక్షికంగా క్రమబద్ధీకరించబడింది' కాదు. 'క్రమబద్ధీకరించు' అనే పదానికి పూర్తి క్రమం (పూర్తి క్రమబద్ధీకరణ) అని అర్థం. ఒక కుప్ప పాక్షికంగా ఏకపక్షంగా ఆర్డర్ చేయబడదు. దిగువ చూపిన విధంగా ఒక కుప్ప పాక్షికంగా ఒక ప్రమాణం (నమూనా)ని అనుసరించి ఆర్డర్ చేయబడింది.
కాబట్టి, హీప్‌సార్ట్ రెండు దశలను కలిగి ఉంటుంది: కుప్పను నిర్మించడం మరియు కుప్ప ఎగువ నుండి ఆర్డర్ చేసిన మూలకాన్ని సంగ్రహించడం. రెండవ దశలో, ప్రతి వెలికితీత తర్వాత, కుప్ప పునర్నిర్మించబడుతుంది. ఒక మూలకం తీసివేయబడిన మునుపటి బిల్డ్ నుండి పునర్నిర్మాణం చేయబడినందున ప్రతి పునర్నిర్మాణం అసలు నిర్మాణ ప్రక్రియ కంటే వేగంగా ఉంటుంది. మరియు దానితో, heapsort పూర్తిగా క్రమబద్ధీకరించని జాబితాను క్రమబద్ధీకరిస్తుంది.
ఈ కథనం యొక్క లక్ష్యం క్లుప్తంగా హెప్‌సార్ట్‌ని వివరించడం మరియు దాని సమయ సంక్లిష్టతను ఉత్పత్తి చేయడం (క్రింద ఉన్న సమయ సంక్లిష్టత యొక్క అర్థాన్ని చూడండి). చివర్లో, C++లో కోడింగ్ జరుగుతుంది.
కనిష్ట కుప్ప
కుప్ప కనిష్ట కుప్ప లేదా గరిష్ట కుప్ప కావచ్చు. గరిష్ట-కుప్ప అంటే మొదటి మూలకం అత్యధిక మూలకం, మరియు మొత్తం చెట్టు లేదా సంబంధిత జాబితా పాక్షికంగా అవరోహణ క్రమంలో ఆర్డర్ చేయబడుతుంది. మిని-హీప్ అంటే మొదటి మూలకం అతి తక్కువ మూలకం మరియు మొత్తం జాబితా పాక్షికంగా ఆరోహణ క్రమంలో ఆర్డర్ చేయబడుతుంది. ఈ వ్యాసంలో, కనీస కుప్ప మాత్రమే పరిగణించబడుతుంది. గమనిక: కుప్ప అంశంలో, ఒక మూలకాన్ని నోడ్ అని కూడా అంటారు.
కుప్ప అనేది పూర్తి బైనరీ చెట్టు. బైనరీ చెట్టును శ్రేణి (జాబితా)గా వ్యక్తీకరించవచ్చు; పై నుండి క్రిందికి మరియు ఎడమ నుండి కుడికి చదవండి. 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 |
ఈ పట్టిక యొక్క మొదటి వరుస శ్రేణి యొక్క మూలకాలు. రెండవ వరుసలో సున్నా-ఆధారిత సూచికలు ఉన్నాయి. మూలకాల యొక్క ఈ జాబితాను చెట్టుగా వ్యక్తీకరించవచ్చు. పూర్తి బైనరీ ట్రీని చేయడానికి శూన్య మూలకాలు జోడించబడ్డాయి. ఖచ్చితంగా చెప్పాలంటే, శూన్య అంశాలు జాబితాలో (చెట్టు) భాగం కాదు. ఈ జాబితాకు ఆర్డర్ లేదు, కాబట్టి ఇది ఇంకా కుప్పగా లేదు. కుప్ప ఆస్తి ప్రకారం పాక్షికంగా ఆర్డర్ చేసినప్పుడు అది కుప్పగా మారుతుంది.
నోడ్స్ మరియు ఇండెక్స్‌ల మధ్య సంబంధం
గుర్తుంచుకోండి, హీప్ కాన్ఫిగరేషన్ (కుప్ప ఆస్తి) కలిగి ఉండటానికి ముందు కుప్ప అనేది పూర్తి బైనరీ చెట్టు. మునుపటి జాబితా ఇంకా కుప్పగా లేదు, ఎందుకంటే మూలకాలు హీప్ ప్రాపర్టీకి కట్టుబడి ఉండవు. మిన్-హీప్ ప్రాపర్టీ ప్రకారం ఎలిమెంట్‌లను పాక్షిక క్రమంలో పునర్వ్యవస్థీకరించిన తర్వాత ఇది కుప్పగా మారుతుంది. పాక్షిక క్రమాన్ని పాక్షిక క్రమపద్ధతిలో చూడవచ్చు (అయితే 'క్రమబద్ధీకరించు' అనే పదానికి పూర్తి క్రమం అని అర్థం).
బైనరీ చెట్టు కుప్ప అయినా కాకపోయినా, ప్రతి పేరెంట్‌కి లీఫ్ (చివరి) నోడ్‌లు తప్ప ఇద్దరు పిల్లలు ఉంటారు. ప్రతి తల్లిదండ్రులు మరియు దాని పిల్లల మధ్య సూచికల మధ్య గణిత సంబంధం ఉంది. ఇది క్రింది విధంగా ఉంది: పేరెంట్ ఇండెక్స్ i వద్ద ఉంటే, ఎడమ పిల్లవాడు సూచికలో ఉంటాడు:
రెండు * i + 1మరియు సరైన పిల్లవాడు సూచికలో ఉన్నాడు:
రెండు * i + రెండుఇది సున్నా-ఆధారిత ఇండెక్సింగ్ కోసం. కాబట్టి, ఇండెక్స్ 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 |
గమనిక: జాబితాలో 12 మూలకాలు ఉన్నాయి మరియు 15 కాదు. రెండవ వరుసలో సూచికలు ఉన్నాయి. కుప్ప నిర్మాణ ప్రక్రియలో, మూలకాలు తనిఖీ చేయబడాలి మరియు కొన్ని మార్చబడ్డాయి.
చిన్న మరియు మొదటి మూలకం 3 అని గమనించండి. మిగిలిన మూలకాలు ఆరోహణ కానీ తరంగాల పద్ధతిలో అనుసరిస్తాయి. 2i+1 మరియు 2i+2 స్థానాల్లో ఉన్న ఎడమ మరియు కుడి పిల్లలు ప్రతి ఒక్కరు i వద్ద ఉన్న తల్లిదండ్రుల కంటే ఎక్కువగా లేదా సమానంగా ఉంటే, ఇది కనిష్ట-కుప్ప. ఇది పూర్తి ఆర్డర్ లేదా సార్టింగ్ కాదు. కుప్ప ఆస్తి ప్రకారం ఇది పాక్షిక క్రమం. ఇక్కడి నుండే కుప్పల క్రమబద్ధీకరణ కోసం తదుపరి దశ ప్రారంభమవుతుంది.
హీపిఫై టైమ్ కాంప్లెక్సిటీ
సమయ సంక్లిష్టత అనేది కొన్ని కోడ్ యొక్క సంబంధిత రన్నింగ్ సమయం. ఆ కోడ్‌ని పూర్తి చేయడానికి ఇది ప్రధాన కార్యకలాపాల సంఖ్యగా చూడవచ్చు. హీప్ బిల్డింగ్ కోసం వివిధ అల్గారిథమ్‌లు ఉన్నాయి. అత్యంత సమర్థవంతమైన మరియు వేగవంతమైనవి నిరంతరం జాబితాను రెండుగా విభజించి, దిగువ నుండి మూలకాలను తనిఖీ చేసి, ఆపై మూలకాల యొక్క కొంత మార్పిడిని చేస్తాయి. జాబితాలోని ప్రాక్టికల్ ఎలిమెంట్‌ల సంఖ్యను 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 x 3=> 24 = 8 x లాగ్ < ఉప > రెండు < / ఉప > 8
లాగ్ నుండి రెండు 8 = 3.
సాధారణంగా, హీప్‌సార్ట్ కోసం సగటు కేసు సమయం సంక్లిష్టత:
ఓ ( n. log2n )డాట్ అంటే గుణకారం మరియు n అంటే N, జాబితాలోని మొత్తం మూలకాల సంఖ్య (జాబితా).
మొదటి మూలకాన్ని సంగ్రహించే ఆపరేషన్ విస్మరించబడిందని గమనించండి. సమయ సంక్లిష్టత అంశంలో, సాపేక్షంగా తక్కువ సమయం తీసుకునే కార్యకలాపాలు విస్మరించబడతాయి.
C++లో కోడింగ్
C++ యొక్క అల్గోరిథం లైబ్రరీలో, make_heap() ఫంక్షన్ ఉంది. వాక్యనిర్మాణం:
టెంప్లేట్ < తరగతి రాండమ్ యాక్సెస్ ఇటరేటర్, తరగతి సరిపోల్చండి >constexpr శూన్యం తయారు_కుప్ప ( ముందుగా రాండమ్‌యాక్సెస్‌ఇటరేటర్, చివరిగా రాండమ్‌యాక్సెస్‌ఇటరేటర్, కంపేర్ కాంప్ ) ;
ఇది వెక్టార్ యొక్క మొదటి మూలకాన్ని సూచించే ఇటరేటర్‌ను దాని మొదటి ఆర్గ్యుమెంట్‌గా తీసుకుంటుంది మరియు వెక్టార్ ముగింపుకు మించిన ఇటరేటర్‌ను దాని చివరి ఆర్గ్యుమెంట్‌గా తీసుకుంటుంది. మునుపటి క్రమబద్ధీకరించని జాబితా కోసం, కనీస కుప్పను పొందేందుకు వాక్యనిర్మాణం క్రింది విధంగా ఉపయోగించబడుతుంది:
వెక్టర్ < int > vtr = { 9 , 19 , 24 , 5 , 3 , పదకొండు , 14 , 22 , 7 , 6 , 17 , పదిహేను } ;వెక్టర్ < int > :: పునరావృతం చేసేవాడు iterB = vtr ప్రారంభం ( ) ;
వెక్టర్ < int > :: పునరావృతం చేసేవాడు iterE = vtr ముగింపు ( ) ;
తయారు_కుప్ప ( iterB, iterE, గ్రేటర్ < int > ( ) ) ;
ఈ కోడ్ వెక్టార్ కంటెంట్‌ను కనిష్ట హీప్ కాన్ఫిగరేషన్‌గా మారుస్తుంది. కింది C++ వెక్టర్స్‌లో, రెండు శ్రేణులకు బదులుగా రెండు వెక్టర్‌లు ఉపయోగించబడతాయి.
వెక్టర్ యొక్క మొదటి మూలకాన్ని కాపీ చేసి, తిరిగి ఇవ్వడానికి, వెక్టర్ సింటాక్స్ ఉపయోగించండి:
constexpr సూచన ముందు ( ) ;వెక్టార్ యొక్క మొదటి మూలకాన్ని తీసివేసి, దానిని విసిరేయడానికి, వెక్టర్ సింటాక్స్ ఉపయోగించండి:
constexpr ఇటరేటర్ ఎరేస్ ( const_iterator స్థానం )వెక్టర్ (తదుపరి మూలకం) వెనుక భాగంలో ఒక మూలకాన్ని జోడించడానికి, వెక్టర్ సింటాక్స్ ఉపయోగించండి:
constexpr శూన్యం వెనుకకు నెట్టడం ( స్థిరంగా టి & x ) ;కార్యక్రమం ప్రారంభం:
##
#
ఉపయోగించి నేమ్‌స్పేస్ std ;
అల్గోరిథం మరియు వెక్టార్ లైబ్రరీలు చేర్చబడ్డాయి. ప్రోగ్రామ్‌లో తదుపరిది హీప్‌సార్ట్() ఫంక్షన్, ఇది:
శూన్యం కుప్పలు ( వెక్టర్ < int > & పాతవి, వెక్టర్ < int > & కొత్తవి ) {ఉంటే ( పాతవి. పరిమాణం ( ) > 0 ) {
వెక్టర్ < int > :: పునరావృతం చేసేవాడు iterB = పాతవి. ప్రారంభం ( ) ;
వెక్టర్ < int > :: పునరావృతం చేసేవాడు iterE = పాతవి. ముగింపు ( ) ;
తయారు_కుప్ప ( iterB, iterE, గ్రేటర్ < int > ( ) ) ;
int తరువాత = పాతవి. ముందు ( ) ;
పాతవి. తుడిచివేయండి ( iterB ) ;
కొత్తవి. వెనుకకు నెట్టడం ( తరువాత ) ;
కుప్పలు ( పాతవి, కొత్తవి ) ;
}
}
ఇది రికర్సివ్ ఫంక్షన్. ఇది C++ అల్గోరిథం లైబ్రరీ యొక్క make_heap() ఫంక్షన్‌ని ఉపయోగిస్తుంది. ఫంక్షన్ డెఫినిషన్‌లోని రెండవ కోడ్ సెగ్మెంట్ హీప్ బిల్డింగ్ తర్వాత పాత వెక్టార్ నుండి మొదటి ఎలిమెంట్‌ను సంగ్రహిస్తుంది మరియు కొత్త వెక్టర్ కోసం తదుపరి మూలకం వలె జోడిస్తుంది. ఫంక్షన్ డెఫినిషన్‌లో, వెక్టార్ పారామితులు సూచనలు అని గమనించండి, అయితే ఫంక్షన్ ఐడెంటిఫైయర్‌లతో (పేర్లు) పిలువబడుతుంది.
దీనికి తగిన C++ ప్రధాన విధి:
int ప్రధాన ( int argc, చార్ ** argv ){
వెక్టర్ < int > పాతవి = { 9 , 19 , 24 , 5 , 3 , పదకొండు , 14 , 22 , 7 , 6 , 17 , పదిహేను } ;
వెక్టర్ < int > కొత్తవి ;
కుప్పలు ( పాతవి, కొత్తవి ) ;
కోసం ( int i = 0 ; i < కొత్తవి. పరిమాణం ( ) ; i ++ ) {
కోట్ << కొత్తవి [ i ] << '' ;
}
కోట్ << endl ;
తిరిగి 0 ;
}
అవుట్‌పుట్:
3 5 6 7 9 పదకొండు 14 పదిహేను 17 19 22 24క్రమబద్ధీకరించబడింది (పూర్తిగా).
ముగింపు
సార్టింగ్ అల్గారిథమ్‌గా సాధారణంగా హీప్‌సార్ట్ అని పిలువబడే హీప్ క్రమబద్ధీకరణ యొక్క స్వభావం మరియు పనితీరు గురించి వ్యాసం వివరంగా చర్చించింది. Heapify టైమ్ కాంప్లెక్సిటీ, Heapsort ఇలస్ట్రేషన్ మరియు Heapsort ఒక అల్గారిథమ్‌గా కవర్ చేయబడ్డాయి మరియు ఉదాహరణల ద్వారా మద్దతు ఇవ్వబడ్డాయి. బాగా వ్రాసిన హీప్‌సార్ట్ ప్రోగ్రామ్‌కి సగటు సమయ సంక్లిష్టత O(nlog(n))