Ora che hai familiarità con cosa sono gli heap e come funzionano, vediamo come l'STL ci consente di manipolarli in C++.
Questa è la parte 2 della nostra serie sugli heap e le code prioritarie:
- Parte 1:Nozioni di base su Heap
- Parte 2:costruzione, smontaggio e smistamento di cumuli (video)
- Parte 3:code, code prioritarie e heap
- Parte 4:Cosa porta Heaps che le code prioritarie non fanno (video)
Trascrizione del video:
Ehi, sono Jonathan Boccara per Fluent C++. Questa è la parte 2 della nostra serie mista di video e articoli su heap e code prioritarie. Se vuoi aggiornarti sulla parte 1, puoi trovarla su Fluent C++, il blog.
In questo video creeremo heap, annulleremo heap e ordineremo heap con STL in C++.
Prendiamo l'esempio di un heap:
Questo è un heap massimo, l'elemento più grande è un top. Inseriamo un elemento. Questo è abbastanza indipendente dal C++, è come inserire un elemento nella struttura dei dati dell'heap.
std::push_heap
Aggiungeremo 8.8 alla fine dell'heap. Questa non è la sua posizione giusta, quindi lo faremo salire nel mucchio. Lo confrontiamo con il suo genitore e, ogni volta che è più grande del suo genitore, li scambiamo insieme:
In questo modo alla fine raggiungerà la sua posizione finale.
In C++, gli heap sono rappresentati come strutture contigue, in std::vector s per esempio. Quindi riduciamo questo mucchio in un array come abbiamo visto nella parte 1 della serie.
Ora per aggiungere un elemento, respingiamo l'elemento alla fine del vettore e chiamiamo std::push_heap , per fare in modo che quest'ultimo elemento raggiunga la sua posizione finale nell'heap:
std::vector myHeap = // ... see Part 1 about std::make_heap myHeap.push_back(8.8); std::push_heap(begin(myHeap), end(myHeap));
std::pop_heap
Ora come rimuoviamo un elemento dall'heap?
Possiamo rimuovere solo un elemento, l'elemento superiore. Per farlo, utilizzeremo std::pop_heap . Si inizia scambiando il primo elemento, di cui vogliamo sbarazzarci, con l'ultimo elemento che è uno dei più piccoli.
E poi farà in modo che quel piccolo elemento, che probabilmente non è nella sua giusta posizione in alto, si fa strada giù per il mucchio fino alla sua posizione finale, confrontandolo con i suoi figli. Ogni volta che è più piccolo di uno dei suoi figli, lo sostituiremo con il suo figlio massimo, per assicurarci di mantenere la proprietà heap.
E per eliminare effettivamente l'elemento che era in cima all'heap e che ora si trova nell'ultima posizione nel vettore, eseguiamo un pop_back sul vettore:
std::pop_heap(begin(myHeap), end(myHeap)); myHeap.pop_back();
std::sort_heap
Ora, se ci pensi, se lo fai std::pop_heap ripetutamente ma senza far tornare indietro gli elementi dal vettore, gli elementi in alto si accumuleranno alla fine del vettore, in ordine.
In questo modo tante volte quanti sono gli elementi nell'heap si ottiene un vettore ordinato e non più heap.
Questo è essenzialmente ciò che std::sort_heap fa:
std::sort_heap(begin(myHeap), end(myHeap));
Prende un heap e lo ordina e la sua complessità è al massimo 2*N*log(N).
Quindi questo è tutto per manipolare gli heap con l'STL. Abbiamo visto come creare heap con std::push_heap , come sbloccare gli heap con std::pop_heap e come ordinare gli heap con std::sort_heap .
Spero che questa serie mista di articoli e video su heap e code di priorità in C++ ti stia divertendo. Se vuoi più video sulle strutture di dati in C++ o più in generale sul codice espressivo in C++ puoi premere quel pulsante rosso appena sotto, iscriviti al canale Fluent C++. E se questo video vi è piaciuto, perché non metterci un pollice in su, ve ne sarei molto grato!
E ci vediamo per la Parte 3 sul blog Fluent C++, fluentcpp.com, per esplorare le code e le code prioritarie.
Grazie e ci vediamo la prossima volta.