Eliminar un elemento del medio de un std::heap

El tutorial o código que verás en este artículo es la solución más sencilla y efectiva que hallamos a esta inquietud o dilema.

Solución:

Supongo que sabe qué elemento del contenedor del montón (índice n) desea eliminar.

1. Establecer el valor v[n] = BIG; el valor BIG es realmente más grande que cualquier otro valor en el montón.
2. Llamar std::push_heap( v.begin(), v.begin()+n+1 );
3. Llamar std::pop_heap( v.begin(), v.end() );
4. Llamar v.pop_back();
5. Hecho

La operación es O(ln(n))

RE: solicitud de prueba

Primero, un calificador: este método asume algo sobre el algoritmo utilizado por std push_heap.
Específicamente, asume que std push_heap( v.begin(), v.begin()+n+1 ) solo alterará el rango [0, n]

para aquellos elementos que son ascendientes de n, es decir, índices en el siguiente conjunto:

A(n)=n,(n-1)/2,((n-1)/2-1)/2....0.  

Aquí hay una especificación típica para std push_heap:

http://www.cplusplus.com/reference/algorithm/push_heap/ “Dado un rango de montón[primero,último-1]esta función extiende el rango considerado un montón a[primero,último]colocando el valor en (último -1) en su ubicación correspondiente en él”. [firstlast-1)thisfunctionextendstherangeconsideredaheapto[firstlast)byplacingthevaluein(last-1)intoitscorrespondinglocationinit”

¿Garantiza el uso del “algoritmo de montón normal” sobre el que lee en los libros de texto? Dígame usted.

De todos modos, aquí está el código que puede ejecutar y ver, empíricamente, que funciona. Estoy usando VC 2005.

#include 
#include 
#include 

bool is_heap_valid(const std::vector &vin)

    std::vector v = vin;
    std::make_heap(v.begin(), v.end());
    return std::equal(vin.begin(), vin.end(), v.begin());



int _tmain(int argc, _TCHAR* argv[])

    srand(0);
    std::vector v;
    for (int i=0; i<100; i++)
    
        v.push_back( rand() % 0x7fff );
    
    std::make_heap(v.begin(), v.end());

    bool bfail = false;
    while( v.size() >= 2)
    
        int n = v.size()/2;
        v[n] = 0x7fffffff;
        std::push_heap(v.begin(), v.begin()+n+1);
        std::pop_heap(v.begin(), v.end());
        v.resize(v.size()-1);
        if (!is_heap_valid(v))
        
            std::cout << "heap is not valid" << std::endl;
            bfail = true;
            break;
        
    
    if (!bfail)
        std::cout << "success" << std::endl;

    return 0;

Pero tengo otro problema, que es como saber el índice "n" que hay que borrar. No puedo ver cómo hacer un seguimiento de eso (conocer el lugar en el montón) mientras uso std push_heap y std pop_heap. Creo que necesita escribir su propio código de montón y escribir el índice en el montón en un objeto cada vez que el objeto se mueve en el montón. Suspiro.

Desafortunadamente, al estándar le falta esta función (bastante importante). Con g ++, puede usar la función no estándar std::__adjust_heap para hacer esto, pero no hay una forma portátil fácil de hacerlo, y __adjust_heap es ligeramente diferente en diferentes versiones de g ++, por lo que ni siquiera puede hacerlo de forma portátil sobre las versiones de g ++.

¿Cómo está tu repair_heap() ¿trabaja? Aquí está mi conjetura:

Si su montón está definido por algún rango de iteradores, digamos (heapBegin, heapEnd). El elemento que desea eliminar es la raíz de algún subárbol del montón, que está definido por algún subrango (subHeapBegin, subHeapEnd). Usar std::pop_heap(subHeapBegin, subHeapEnd)Entonces sí subHeapEnd != heapEndintercambie los valores en *(subHeapEnd-1) y *(heapEnd-1), que debería poner su elemento eliminado al final del contenedor de montón. Ahora tiene que filtrar el elemento en *(subHeapEnd-1) en su submontón. Si no me he perdido nada, lo cual es posible, todo lo que queda es cortar el elemento final del contenedor del montón.

Antes de tomarme la molestia de tratar de codificar eso correctamente (me salté algunos detalles como calcular subHeapBegin y subHeapEnd), ejecutaría algunas pruebas para determinar si make_heap() realmente te ralentiza. Big-O es útil, pero no es lo mismo que el tiempo de ejecución real.

valoraciones y reseñas

Si sostienes algún recelo o capacidad de afinar nuestro tutorial eres capaz de dejar una explicación y con placer lo analizaremos.

---

---

Utiliza Nuestro Buscador