diccionario prioridad

Question

C++ que necesitan un contenedor para almacenar pares, tengo dos operaciones:

1. valor de actualización de clave
2. conseguir la llave con valor máximo.

Para la primera operación, el mapa es una buena estructura. Para la segunda operación, parece que la cola de prioridad es buena. ¿Cómo harías esto? ¿Hay alguna forma de tener ambas dos operaciones sin tener un bucle O (n)? Gracias.

Answer 1

Una solución asintóticamente eficiente a este sería el uso de una combinación de una tabla hash y un montón de Fibonacci. Utilizaría la tabla hash para poder acceder al valor asociado con cualquier clave en particular en O (1) tiempo, y usaría el montón Fibonacci para poder buscar rápidamente el par clave/valor con el valor más bajo (haciéndolo así en O (1)).

Si desea cambiar el valor asociado con una tecla, si está aumentando el valor, puede hacerlo en tiempo (amortizado) O (1) utilizando la operación de aumento de la tecla en el montón de Fibonacci, que tiene O (1) tiempo amortizado. Si está disminuyendo el valor, tardará O (log n) en eliminar el elemento del montón de Fibonacci y luego volverá a insertarlo.

En general, esto da una complejidad de tiempo de

• insertar un nuevo elemento: O (1) para de hash, O (1) para la inserción en Fibonacci montón: O (1) Tiempo de.
• Eliminar un elemento: O (1) para hash, O (log n) para eliminar del montón de Fibonacci: O (log n) time.
• Buscar elemento superior: O (1) para búsqueda en Fibonacci montón: O (1) tiempo.
• Aumente un valor: O (1) para el hash, O (1) para la tecla de aumento: O (1) hora.
• Disminuya un valor: O (1) para hash, O (log n) para eliminar/insertar: O (log n) time.

Hope this helps!

Answer 2

Crea un heap structure (para la segunda viñeta) y coloca cada uno de sus nodos en un mapa (para la primera viñeta).

EDIT: Una implementación del montón minutos que había hecho alguna vez en el pasado

#ifndef MINHEAP_H 
#define MINHEAP_H 

//////////////////////// MinHeap with Map for Data //////////////////////// 

template <class T, class M = int> class MinHeap { 
    T*   array; 
    unsigned const int arr_max; 
    unsigned int  elements; 
    M   map; 

    void percolate_down(unsigned int i=0) { 
     unsigned int n = elements-1, min; 
     do { 
      unsigned int l = 2*i + 1, r = 2*i + 2; 
      if (l <= n && array[i] > array[l]) min = l; 
      else min = i; 
      if (r <= n && array[i] > array[r] && array[l] > array[r]) min = r; 
      if (i != min) { 
       T temp = array[i]; 
       array[i] = array[min]; 
       array[min] = temp; 
       map.update(array[i], i); 
       map.update(array[min], min); 
       i = min; 
      } else break; 
     } while (i < n); 
    } 
    void percolate_up(unsigned int i) { 
     while (i && array[(i-1)/2] > array[i]) { 
      T temp = array[i]; 
      array[i] = array[(i-1)/2]; 
      array[(i-1)/2] = temp; 
      map.update(array[i], i); 
      map.update(array[(i-1)/2], (i-1)/2); 
      i = (i-1)/2; 
     } 
    } 
public: 
    MinHeap(const int max) : array(new T[max]), arr_max(max), elements(0), map(max) {} 
    ~MinHeap(void) { delete[] array; } 

    bool empty(void) const { return elements == 0; } 
    unsigned int capacity(void) const { return arr_max; } 
    unsigned int size(void) const { return elements; } 
    const M& heapmap(void) const { return map; } 
    const T& peek(unsigned int i=0) const { return array[i]; } 

    bool insert(T& element) { 
     if (arr_max == elements) return false; 

     unsigned int k = elements++; 
     map.update(element, k); 
     array[k] = element; 
     percolate_up(k); 
     return true; 
    } 
    unsigned int mass_insert(T copy[], unsigned int n) { 
     unsigned int i = 0;  
     for(; i < n ; i++) if (!insert(copy[i])) break; 
     return i; 
    } 
    bool delete_min(void) { 
     if (elements == 0) return false; 

     map.update(array[0], arr_max+1); 
     array[0] = array[--elements]; 
     map.update(array[0], 0); 
     percolate_down(); 
     return true; 
    } 
    bool delete_element(unsigned int i) { 
     if (i > elements) return false; 

     map.update(array[i], arr_max+1); 
     T temp = array[i];  
     array[i] = array[--elements]; 
     map.update(array[i], i); 
     if (array[i] > temp) percolate_down(i); 
     else if (temp > array[i]) percolate_up(i); 
     return true; 
    } 
    bool update(unsigned int i, T& element) { 
     if (i > elements) return false; 

     map.update(array[i], arr_max+1); 
     T temp = array[i];  
     array[i] = element; 
     map.update(array[i], i); 
     if (array[i] > temp) percolate_down(i); 
     else if (temp > array[i]) percolate_up(i); 
     return true; 
    } 

// void print() { using namespace std; for (unsigned int i=0 ; i < elements ; i++) cout << array[i] << " | "; cout << endl; } 


    // Iterators 
/* 
    friend class Const_Iterator; 

    class Const_Iterator { 
     MinHeap<T>* heap; 
     unsigned int index; 
     Const_Iterator(MinHeap<T>* h, unsigned int i) : heap(h), index(i) {} 
    public: 
     Const_Iterator(const Const_Iterator& clone) : heap(clone.heap), index(clone.index) {} 

     friend Const_Iterator MinHeap<T>::begin(void); 
    }; 

    Const_Iterator begin(void) { return Const_Iterator(this, 0); } 
*/ 
}; 

////////////////////////////////////////////////////////////////////////////// 


//////////////////////// MinHeap without Map for Data //////////////////////// 

template <class T> class MinHeap <T, int> { 
    T*   array; 
    unsigned const int arr_max; 
    unsigned int  elements; 

    void percolate_down(unsigned int i=0) { 
     unsigned int n = elements-1, min; 
     do { 
      unsigned int l = 2*i + 1, r = 2*i + 2; 
      if (l <= n && array[i] > array[l]) min = l; 
      else min = i; 
      if (r <= n && array[i] > array[r] && array[l] > array[r]) min = r; 
      if (i != min) { 
       T temp = array[i]; 
       array[i] = array[min]; 
       array[min] = temp; 
       i = min; 
      } else break; 
     } while (i < n); 
    } 
    void percolate_up(unsigned int i) { 
     while (i && array[(i-1)/2] > array[i]) { 
      T temp = array[i]; 
      array[i] = array[(i-1)/2]; 
      array[(i-1)/2] = temp; 
      i = (i-1)/2; 
     } 
    } 
public: 
    MinHeap(const int max) : array(new T[max]), arr_max(max), elements(0) {} 
    ~MinHeap(void) { delete[] array; } 

    bool empty(void) const { return elements == 0; } 
    unsigned int capacity(void) const { return arr_max; } 
    unsigned int size(void) const { return elements; } 
    const T& peek(unsigned int i=0) const { return array[i]; } 

    bool insert(T& element) { 
     if (arr_max == elements) return false; 

     unsigned int k = elements++; 
     array[k] = element; 
     percolate_up(k); 
     return true; 
    } 
    unsigned int mass_insert(T copy[], unsigned int n) { 
     unsigned int i = 0;  
     for(; i < n ; i++) if (!insert(copy[i])) break; 
     return i; 
    } 
    bool delete_min(void) { 
     if (elements == 0) return false; 

     array[0] = array[--elements]; 
     percolate_down(); 
     return true; 
    } 
    bool delete_element(unsigned int i) { 
     if (i > elements) return false; 

     T temp = array[i];  
     array[i] = array[--elements]; 
     if (array[i] > temp) percolate_down(i); 
     else if (temp > array[i]) percolate_up(i); 
     return true; 
    } 
    bool update(unsigned int i, T& element) { 
     if (i > elements) return false; 

     T temp = array[i];  
     array[i] = element; 
     if (array[i] > temp) percolate_down(i); 
     else if (temp > array[i]) percolate_up(i); 
     return true; 
    } 

// void print() { using namespace std; for (unsigned int i=0 ; i < elements ; i++) cout << array[i] << " | "; cout << endl; } 
}; 

////////////////////////////////////////////////////////////////////////////// 

#endif // MINHEAP_H 

Answer 3

impulso :: BIMAP podría hacer lo que quiera, donde el mapa inversa se utiliza para implementar # 2.

Answer 4

creo que el BIMAP es la mejor ruta

Answer 5

Según mi C++ 0x estándar, The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them.

Entonces sólo tiene que utilizar un mapa. La búsqueda aleatoria es O (log (n)), y para obtener el elemento más alto toma O (1) vez.

value getHighest(map<key, value>& map) { 
    assert(map.empty() == false); 
    return (--map.end())->second; 
}