C++ dizionario priorità

Question

ho bisogno di un contenitore per memorizzare coppie, ho due operazioni:

1. valore di aggiornamento chiave
2. ottenere la chiave con valore massimo.

Per la prima operazione, la mappa è una buona struttura. Per la seconda operazione, sembra che la coda di priorità sia buona. come lo faresti? Esiste comunque la possibilità di eseguire entrambe le operazioni senza un ciclo O (n)? Grazie.

Answer 1

Una soluzione asintoticamente efficiente per questo sarebbe quella di utilizzare una combinazione di una tabella di hash e un mucchio di Fibonacci. Dovresti usare la tabella hash per poter accedere al valore associato a una particolare chiave in O (1) volta, e userei l'heap di Fibonacci per essere in grado di cercare rapidamente la coppia chiave/valore con il valore più basso (facendo così in O (1)).

Se si desidera modificare il valore associato a un tasto, se si aumenta il valore, è possibile farlo in (O) (tempo) ammortizzato utilizzando l'operazione di incremento-tasto sull'heap di Fibonacci, che ha O (1) tempo ammortizzato. Se si sta riducendo il valore, occorrerà O (log n) per eliminare l'elemento dall'heap di Fibonacci e quindi reinserirlo.

Nel complesso, questo dà una complessità temporale di

• inserire un nuovo elemento: O (1) per hash, O (1) per l'inserimento in Fibonacci heap: O (1) tempo.
• Elimina un elemento: O (1) per hash, O (log n) per eliminazione dall'heap di Fibonacci: O (log n) tempo.
• Trova l'elemento superiore: O (1) per la ricerca nell'heap di Fibonacci: O (1) ora.
• Aumentare un valore: O (1) per cancelletto, O (1) per tasto di incremento: Ora O (1).
• Diminuire un valore: O (1) per hash, O (log n) per eliminare/inserire: O (log n) ora.

Spero che questo aiuti!

Answer 2

Creare un heap structure (per il secondo punto elenco) e inserire ciascuno dei suoi nodi in una mappa (per il primo punto elenco).

EDIT: Un'implementazione di heap min avevo fatto un po 'di tempo in passato

#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

boost :: bimap poteva fare quello che vuoi, dove la mappa inversa viene utilizzato per implementare # 2.

Answer 4

Credo che il bimap è il percorso migliore

Answer 5

Secondo la mia C++ 0x standard 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.

Quindi, basta usare una mappa. La ricerca casuale è O (log (n)), e per ottenere l'elemento più alto è necessario O (1) tempo.

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