2011-08-30 20 views
6

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

  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.

Respuesta

7

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!

+0

¡Esta es una buena solución! También debe tener en cuenta los inconvenientes: mantenerlos sincronizados y el uso de la memoria. –

+0

@Mooing Duck: lo ideal es que envuelvas esto en su propia clase para que no puedas sincronizar los dos. Y sí, hay más uso de memoria, aunque solo es un factor constante más que tener solo una de las dos estructuras. – templatetypedef

+0

@templatetypedef: +1, ¿pero un montón de Fibonacci en lugar de un montón binario (o nary-heap) realmente? Entiendo que los límites teóricos amortizados pueden ser mejores, pero ¿es así prácticamente? Ver, por ejemplo: http://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently. Además, ¿los montones de Fibonaaci en realidad no tienen la peor complejidad del peor caso para algunas operaciones? –

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 
+0

También podría usar 'std :: priority_queue'. – Dawson

+0

@Toolbox Una estructura de montón es una forma de implementar una priority_queue :) –

+0

Lo sé, lo que quise decir es que no hay necesidad de volver a implementar lo que ya es parte de C++ estándar. – Dawson

2

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

+0

¿Qué pasa si varias llaves tienen el mismo valor? – templatetypedef

+0

@templatetypedef: su elección, varios índices son posibles, como 'bimap >'. –

0

creo que el BIMAP es la mejor ruta

+0

¿Qué pasa si varias claves tienen el mismo valor asociado a ellas? – templatetypedef

1

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; 
} 
+0

¿Es esto mantener para el mapa hash? entonces la búsqueda también sería O (1) – user875367

+0

No, los hashes están desordenados, por lo que no puede encontrar el elemento más alto. –