¿Cuál es el punto de make_heap?

Question

¿Puede alguien decirme por favor el objetivo del montón de STL como make_heap? ¿Por qué alguien alguna vez los usaría? ¿Hay un uso práctico?

Answer 1

Si desea hacer una priority queue a cabo de una lista, así, puede utilizar make_heap:

Internamente, un montón es un árbol donde cada nodo se vincula a valores no mayores que su propio valor. En montones generado por make_heap, la posición específica de un elemento en el árbol en lugar de siendo determinada por la memoria que consume enlaces está determinada por su posición absoluta en la secuencia, con * primero ser siempre el valor más alto en el montón.

Montones permiten añadir o eliminar elementos de ella en tiempo logarítmica mediante el uso de funciones push_heap y pop_heap, que conservan sus propiedades montón.

Answer 2

Se utilizan para construir y mantener la Heap data structure

Answer 3

Además de lo anterior, el algoritmo de clasificación de la STL es introsort, que es una mezcla de quicksort y heapsort (falla por encima del quicksort a HeapSort si el primero va mal). make_heap crea una estructura de montón, que es necesaria para ejecutar heapsort, que es necesaria para introsort.

Answer 4

Su pregunta directa sería bien respondida por una clase en algoritmos y estructuras de datos. Los montones se usan en todo el lugar en algoritmos de informática. Para citar de la función make_heap vinculada a continuación, "un montón es un árbol donde cada nodo se vincula a valores no superiores a su propio valor". Si bien hay muchas aplicaciones para un montón, la que uso con más frecuencia es en problemas de búsqueda cuando desea realizar un seguimiento de una lista ordenada de N valores de manera eficiente.

Tuve una confusión similar a la tuya cuando encontré por primera vez las funciones de pila de STL. Mi pregunta era un poco diferente sin embargo. Me preguntaba "¿Por qué el montón de STL no está en la misma clase de estructuras de datos que std :: vector?" Pensé que debería funcionar así:

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

La idea detrás de las funciones STL montón embargo, es que le permiten hacer una estructura de datos montón de varios diferentes contenedores STL subyacentes, incluyendo std :: vector. Esto puede ser realmente útil si desea pasar el contenedor para usarlo en otro lugar de sus programas. También es un poco agradable, porque puedes elegir el contenedor subyacente de tu pila si eliges usar algo distinto de std :: vector. Todo lo que necesita son los siguientes:

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

Esto significa que usted puede hacer un montón de diferentes contenedores en un montón Un comparador es también opcional en la firma del método, se puede leer más acerca de las diferentes cosas que usted puede intentar en las páginas STL para la función make_heap.

Enlaces:

• Heap Data Structure
• make_heap function

Answer 5

Se supone que para utilizar junto con std::make_heap()std::push_heap() y std::pop_heap() para mantener una pila binaria en la parte superior de un vector o matriz; las últimas dos funciones mantienen el montón invariante. También puede usar std::heap_sort() para ordenar dicho montón. Si bien es cierto que puede usar std::priority_queue para una cola de prioridad, no le permite entrar en su interior, lo que quizás quiera hacer. Además, std::make_heap() y std::heap_sort() juntos hacen una forma muy simple de hacer heapsort en C++.

Answer 6

Existen básicamente dos formas de construir un montón [binario]: crear un montón vacío e insertar cada elemento en uno de uno en uno, o tomar un rango de valores y heapificarlos.

Cada operación de inserción en un montón toma el tiempo O (logn) así que si está empujando N elementos en un montón, tomará O (NlogN) el tiempo. Sin embargo, construir un montón binario a partir de una matriz de valores toma solo O (N) tiempo.

Por lo tanto, tiene más sentido insertar cada elemento en una matriz (u otro contenedor que admita iteradores de acceso aleatorio) y luego llamar a make_heap() en la matriz para mantener la estructura de la pila durante la inserción.

Answer 7

std::make_heap casi nunca debe utilizarse en la práctica. Si bien es cierto que los montones son útiles para colas de prioridad, eso no explica por qué querría mantener manualmente la estructura. std::priority_queue tiene una interfaz mucho más útil si todo lo que necesita es una cola de prioridad.

Si usa make_heap y sus hermanos directamente, debe asegurarse de usarlos cada vez que realice un cambio en el contenedor subyacente. Los he visto usar dos o tres veces y cada vez se usaron incorrectamente.

Solo he usado las operaciones de montón directamente una vez, porque necesitaba usar un vector como cola de prioridad por un tiempo y luego ordenarlo. Lo más probable es que nunca necesite std::make_heap.

Si necesita una cola de prioridad con la capacidad de cambiar elementos, puede usar std::set. Puede obtener el elemento más pequeño o más grande con *s.begin() o *s.rbegin() respectivamente y actualizar un elemento eliminando el valor anterior e insertando el nuevo.