Qual è il punto di make_heap?

Question

Qualcuno può dirmi il punto delle funzioni di heap STL come make_heap? Perché mai qualcuno li userebbe? C'è un uso pratico?

Answer 1

Se si vuole fare un priority queue fuori da una lista, beh, è ​​possibile utilizzare make_heap:

Internamente, un mucchio è un albero in cui ogni nodo collega a valori non superiori a rispetto al proprio valore. In cumuli generato dal make_heap, la posizione specifica di un elemento nell'albero anziché essendo determinata dalla memoria consumata link è determinato dalla sua assoluta posizione nella sequenza, con * prima essendo sempre il valore più alto nel heap.

Cumuli permettono di aggiungere o rimuovere elementi da esso in tempo logaritmico utilizzando funzioni push_heap e pop_heap, che mantenere le proprietà mucchio.

Answer 2

Essi sono utilizzati per costruire e mantenere la Heap data structure

Answer 3

In aggiunta a quanto sopra, algoritmo di ordinamento del STL è introsort, che è una miscela di quicksort e heapsort (fallisce sulla Quicksort al heapsort se il primo sta facendo male). make_heap crea una struttura heap, necessaria per eseguire heapsort, necessaria per l'introsortamento.

Answer 4

La tua domanda diretta sarebbe ben fornita da una classe in algoritmi e strutture dati. Gli heap sono usati dappertutto negli algoritmi in informatica. Per citare la funzione make_heap collegata sotto, "un heap è un albero in cui ogni nodo si collega a valori non superiori al suo valore". Mentre ci sono molte applicazioni per un heap, quella che uso più frequentemente è nei problemi di ricerca quando si desidera tenere traccia di un elenco ordinato di N valori in modo efficiente.

Ho avuto una confusione simile alla tua quando ho incontrato per la prima volta le funzioni di heap STL. La mia domanda era un po 'diversa però. Mi chiedevo "Perché l'heap STL non è nella stessa classe di strutture dati di std :: vector?" Ho pensato che dovrebbe funzionare in questo modo:

std::heap<int> my_heap; 
my_heap.heap_insert(7); 
my_heap.heap_insert(3); 

L'idea alla base delle funzioni STL heap però è che essi permettono di fare una struttura dati heap di diversi contenitori STL sottostanti, tra cui std :: vector. Questo può essere davvero utile se vuoi passare il contenitore per utilizzarlo altrove nei tuoi programmi. È anche un po 'bello, perché puoi scegliere il contenitore sottostante del tuo heap se scegli di usare qualcosa di diverso da std :: vector. Tutto ciò che serve sono le seguenti:

template <class RandomAccessIterator> 
    void make_heap (RandomAccessIterator first, RandomAccessIterator last); 

Ciò significa che è possibile fare un sacco di contenitori diversi in un mucchio Un comparatore è anche facoltativa nella firma del metodo, si può leggere di più sulle diverse cose che si possono provare nelle pagine STL per la funzione make_heap.

vicini:

• Heap Data Structure
• make_heap function

Answer 5

si suppone di utilizzare std::make_heap() con std::push_heap() e std::pop_heap() di mantenere un heap binario sulla cima di un vettore o di una matrice; le ultime due funzioni mantengono invariato l'heap. Puoi anche usare std::heap_sort() per ordinare un simile heap. Anche se è vero che potresti usare std::priority_queue per una coda di priorità, non ti permette di entrare nel suo interno, che forse vuoi fare. Inoltre, std::make_heap() e std::heap_sort() insieme fanno un modo molto semplice di fare heapsort in C++.

Answer 6

Ci sono essenzialmente due modi per costruire un heap [binario]: creare un heap vuoto e inserire ciascun elemento in esso uno alla volta, oppure prendere un intervallo di valori e ingrandirli.

Ogni operazione di push su un heap richiede il tempo O (logn), quindi se si stanno spingendo N elementi su un heap ci vorrà tempo O (NlogN). Tuttavia per costruire un heap binario da una matrice di valori richiede solo O (N).

Quindi ha più senso inserire ogni elemento in una matrice (o in un altro contenitore che supporta iteratori di accesso casuale) e quindi chiamare make_heap() sull'array piuttosto che per mantenere la struttura dell'heap durante l'inserimento.

Answer 7

std::make_heap dovrebbe quasi mai essere utilizzato in pratica. Se è vero che gli heap sono utili per le code di priorità, ciò non spiega il motivo per cui si desidera mantenere manualmente la struttura. std::priority_queue ha un'interfaccia molto più utile se tutto ciò che serve è una coda di priorità.

Se si utilizza direttamente make_heap ei suoi fratelli, è necessario assicurarsi di utilizzarli ogni volta che si apporta una modifica al contenitore sottostante. Li ho visti usati due o tre volte e ogni volta sono stati utilizzati in modo errato.

Ho usato le operazioni di heap solo una volta sola, perché avevo bisogno di usare un vettore come coda di priorità per un po 'e poi ordinarlo. Molto probabilmente non avrai mai bisogno di std::make_heap.

Se è necessaria una coda di priorità con la possibilità di modificare gli elementi, è possibile utilizzare std::set. È possibile ottenere l'elemento più piccolo o più grande con *s.begin() o *s.rbegin() rispettivamente e aggiornare un elemento rimuovendo il vecchio valore e inserendo quello nuovo.