Eliminar un elemento del medio de std :: heap

Question

Estoy usando una cola de prioridad como programador con un requerimiento adicional. Necesito poder cancelar artículos programados. Esto equivale a eliminar un elemento del medio de la cola de prioridad.

No puedo usar std::priority_queue ya que el acceso a cualquier elemento que no sea superior está protegido.

Estoy tratando de usar las funciones de montón de algorithm. Pero todavía me falta la pieza que necesito. Cuando elimino un elemento I de la mitad del montón, quiero que se reconstruya de manera eficiente. C++ proporciona estas funciones de montón:

• std::make_heapO (3n)
• std::push_heapO (lg (n))
• std::pop_heapO (2 lg (n))

Quiero una nueva función como std::repair_heap con un gran O < 3n. Le proporcionaría la ubicación del agujero donde solía residir el elemento cancelado y ajustaría correctamente el montón.

Parece ser un gran descuido el no proporcionar una función std::repair_heap. ¿Me estoy perdiendo algo obvio?

¿Hay una biblioteca que proporcione un stl-obediente std::repair_heap?

¿Existe una mejor estructura de datos para modelar un programador?

NOTA:
no estoy usando un std::map por varias razones.

• Un montón tiene una carga de memoria constante.
• Un montón tiene una localidad de memoria caché impresionante.

Answer 1

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 manera fácil de hacerlo, y __adjust_heap es ligeramente diferente en diferentes versiones de g ++, por lo que no puede hacerlo de forma portátil en versiones de g ++ .

Answer 2

Me parece que la eliminación de la mitad de un montón podría significar toda la pila tiene que ser reconstruido: La razón por la que no hay repair_heap se debe a que tendría que hacer lo mismo (oh-grande) trabajo como make_heap .

¿Eres capaz de hacer algo como poner std::pair<bool, Item> en el montón y simplemente invalidar elementos en lugar de eliminarlos? Luego, cuando finalmente lleguen a la cima, simplemente ignoren el elemento y avancen.

Answer 3

¿Cómo funciona su repair_heap()? Aquí está mi conjetura:

Si su montón está definido por algún rango de iterador, 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 subintervalo (subHeapBegin, subHeapEnd).Utilice std::pop_heap(subHeapBegin, subHeapEnd), luego, si subHeapEnd != heapEnd, cambie los valores a *(subHeapEnd-1) y *(heapEnd-1), que debe poner su elemento eliminado al final del contenedor de pila. Ahora tiene que filtrar el elemento en * (subHeapEnd-1) en su subpaso. Si no me he perdido algo, lo cual es posible, entonces todo lo que queda es cortar el elemento final del contenedor del montón.

Antes de tomarse la molestia de intentar codificarlo correctamente (me salté algunos detalles como calcular subHeapBegin y subHeapEnd), realicé algunas pruebas para determinar si make_heap() realmente lo ralentiza. Big-O es útil, pero no es lo mismo que el tiempo de ejecución real.

Answer 4

Aquí hay un poco del código delphi que utilicé para eliminar elementos de un montón. No sé esto C++ de que hablar y no tiene una función de reparación, pero bueno ..

primero el estallido, para que pueda obtener una idea de cómo funciona la cosa:

function THeap.Pop: HeapItem; 
begin 
    if fNextIndex > 1 then begin 
    Dec(fNextIndex); 
    Result:= fBuckets[1]; //no zero element 
    fBuckets[1] := fBuckets[fNextIndex]; 
    fBuckets[fNextIndex] := nil; 
    FixHeapDown;   //this has a param defaulting to 
    end 
    else 
    Result:= nil; 
end; 

ahora contrastar, la eliminación:

procedure THeap.Delete(Item: HeapItem); 
var 
    i:integer; 
begin 
    for i:=1 to pred(fNextIndex) do 
    if Item=fBuckets[i] then begin 
     dec(fNextIndex); 
     fBuckets[i] := fBuckets[fNextIndex]; 
     fBuckets[fNextIndex] := nil; 
     FixHeapDown(i); 
     break; 
     end; 
end; 

su supuesto un no-no para pensar en haciendo lo que estamos haciendo aquí, pero bueno, los costes no cambian veces y trabajos no se cancelan.

enjoy. Espero que esto ayude.

Answer 5

Supongo que sabe qué elemento del contenedor de montón (índice n) que 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. Call std::push_heap(v.begin(), v.begin()+n+1);
3. Call std::pop_heap(v.begin(), v.end());
4. Call v.pop_back();
5. Hecho

operación es O (ln (n))

RE: solicitud de prueba

primer lugar, una calificador: Este método supone algo sobre el al gorithm utilizado por std push_heap.
Específicamente, supone que std push_heap (v.begin(), v.begin() + n + 1) solo alterará el rango [0, n]
para aquellos elementos que son ascendentes de n, es decir, índices en el siguiente conjunto:

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

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

http://www.cplusplus.com/reference/algorithm/push_heap/ "Dada una gama montón [primero, último-1), esta función se extiende el rango considerado un montón de [primero, último) colocando el valor en (last-1) en su ubicación correspondiente en él. "

¿Le garantiza usar el "algoritmo de montón normal" sobre el que lee en los libros de texto? Me dices.

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

#include <algorithm> 
#include <vector> 
#include <iostream> 

bool is_heap_valid(const std::vector<int> &vin) 
{ 
    std::vector<int> 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<int> 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 la manera de saber el índice "n" que debe ser eliminado. 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 a un objeto cada vez que el objeto se mueva en el montón. Suspiro.