Môže mi niekto, prosím, povedať, že funkcia STL haldy funguje ako make_heap? Prečo by ich niekto používal? Existuje praktické využitie?
odpovede:
18 pre odpoveď č. 1Ak chcete urobiť priority frontu zo zoznamu, môžete použiť make_heap:
Vnútri je halda strom, kde každý uzolodkazy na hodnoty nie sú väčšie hodnoty. V hromadách vytvorených podľa make_heap, špecifickej pozície prvok v strome namiesto určujú spotrebu pamäte väzby je určená jej absolútnou hodnotou pozíciu v sekvencii, s prvou * je vždy najvyššia hodnota v haldy.
Hrebene umožňujú pridávať alebo odstraňovať prvky pomocou logaritmického času funkcie push_heap a pop_heap, ktoré si zachovávajú svoje vlastnosti haldy.
41 pre odpoveď č. 2
Vaša priama otázka by bola dobre zodpovedaná atriedy v algoritmoch a dátových štruktúrach. Hromady sa používajú všade v algoritmoch v informatike. Ak chcete citovať z funkcie make_heap prepojenej nižšie, "halda je strom, kde každý uzol spája hodnoty nie väčšie ako jeho vlastná hodnota." Aj keď existuje veľa aplikácií pre haldu, ten, ktorý používam najčastejšie, je pri problémoch s vyhľadávaním, keď chcete efektívne sledovať triedený zoznam hodnôt N.
Mal som podobný zmätok vo vašom, keď som prvýkrátsa vyskytli funkcie haldy STL. Moja otázka však bola trochu iná. Zaujímalo by ma "Prečo nie je STL halda v rovnakej triede dátových štruktúr ako std :: vector?" Myslel som, že by to malo fungovať takto:
std::heap< int > my_heap;
my_heap.heap_insert( 7 );
my_heap.heap_insert( 3 );
Myšlienka funkcie STL haldy je všakumožňujú, aby sa z niekoľkých rôznych podkladových kontajnerov STL vytvorila štruktúra údajov haldy, vrátane std :: vector. To môže byť naozaj užitočné, ak chcete prejsť okolo kontajnera pre použitie inde v programoch. Je to tiež trochu pekné, pretože si môžete vybrať základný kontajner vašej haldy, ak sa rozhodnete použiť niečo iné ako std :: vector.
template <class RandomAccessIterator>
void make_heap ( RandomAccessIterator first, RandomAccessIterator last );
To znamená, že môžete robiť veľa rôznychkontajnery do haldy Komparátor je tiež voliteľný v podpise metódy, môžete si prečítať viac o rôznych veciach, ktoré môžete vyskúšať na stránkach STL pre funkciu make_heap.
odkazy:
7 pre odpoveď č. 3
std::make_heap takmer nikdy v praxi. Aj keď je pravda, že hromady sú užitočné pre prioritné fronty, to nevysvetľuje, prečo by ste chceli zachovať štruktúru. std::priority_queue má oveľa užitočnejšie rozhranie, ak všetko, čo potrebujete, je fronta priorít.
Ak používate make_heap a jeho súrodenci priamo, musíte sa uistiť, že ich použijete zakaždým, keď urobíte zmenu v podkladovom kontajneri. Videl som ich používať dvakrát alebo trikrát a každý jeden raz boli použité nesprávne.
Operácie haldy som použil len raz sám, pretože som potreboval nejaký čas použiť vektor ako prioritný front a potom ho triediť. S najväčšou pravdepodobnosťou nikdy nebudete potrebovať std::make_heap.
Ak potrebujete prioritný front so schopnosťou meniť prvky, môžete použiť std::set, Môžete získať najmenší alebo najväčší prvok pomocou *s.begin() alebo *s.rbegin() a aktualizovať prvok odstránením starej hodnoty a vložením novej.
5 pre odpoveď č. 4
Mali by ste používať std::make_heap() spolu s std::push_heap() a std::pop_heap() na udržanie binárnej haldy na vrchole vektora alebo poľa; posledné dve funkcie zachovávajú invariantnosť haldy. Môžete tiež použiť std::heap_sort() triediť takúto hromadu. Aj keď je pravda, že by ste mohli použiť std::priority_queue pre prioritný front vám neumožňuje dostať sa do vnútra, ktoré možno chcete urobiť. std::make_heap() a std::heap_sort() spolu robia veľmi jednoduchý spôsob, ako robiť heapsort v C ++.
4 pre odpoveď č. 5
Okrem vyššie uvedeného je STL "s triediaci algoritmus je. \ T introsort, čo je zmes quicksortu a heapsortu(to zlyhá z quicksort na heapsort, ak prvý robí zle). make_heap vytvorí štruktúru haldy, ktorá je potrebná pre beh heapsort, ktorý je potrebný pre introsort.
4 pre odpoveď č. 6
Existujú v podstate dva spôsoby, ako konštruovať [binárnu] haldu: vytvorte prázdnu haldu a vložte do nej každý prvok jeden po druhom, alebo si vezmite rozsah hodnôt a zrealizujte ich.
Každá operácia push na halde trvá čas O (logn), takže ak tlačíte položky N na haldu, bude trvať čas O (NlogN). Avšak na vytvorenie binárnej haldy z poľa hodnôt trvá len čas O (N).
Preto má väčší zmysel vkladať každý prvokdo poľa (alebo iného kontajnera, ktorý podporuje iterátory s náhodným prístupom) a potom zavolajte make_heap () na pole, než aby sa zachovala štruktúra haldy pri vkladaní.
2 pre odpoveď č. 7
Používajú sa na konštrukciu a údržbu Štruktúra dát haldy