2011-08-30 68 views
6

我需要一個容器來儲存對,我有兩個操作:C++優先字典

  1. 更新通過關鍵
  2. 價值得到最大價值的關鍵。

對於第一個操作,map是一個很好的結構。對於第二個操作,似乎優先隊列是一個好的隊列。你會如何做到這一點?無論如何,在沒有O(n)循環的情況下完成這兩個操作? 謝謝。

回答

7

漸近高效的解決方案,這將是使用哈希表和斐波那契堆的組合的最佳路線。您將使用散列表訪問與O(1)時間內的任何特定鍵相關聯的值,並使用斐波那契堆以便能夠快速查找具有最低值的鍵/值對(這樣做在O(1))。

如果要更改與某個鍵相關聯的值,如果要增加該值,則可以在(分期償還)O(1)時間內通過使用斐波那契堆上的增加鍵操作完成此操作,該操作具有O(1)攤銷時間。如果你正在減少這個值,它將花費O(log n)時間從斐波那契堆中刪除該元素,然後重新插入它。

總體而言,這給出了

  • 一個時間複雜度插入一個新元素:O(1)對於哈希,O(1),用於插入到斐波那契堆:O(1)時間
  • 刪除一個元素:O(1)爲散列,O(log n)從斐波那契堆中刪除:O(log n)時間
  • 查找頂部元素:O(1)查找斐波那契堆:O(1)時間。
  • 增加值:O(1)爲散列,O(1)爲增加鍵:O(1)時間。
  • 減小值:O(1)爲散列,O(log n)爲刪除/插入:O(log n)時間。

希望這會有所幫助!

+0

這是一個很好的解決方案!儘管如此,你還應該注意到它們的缺點:保持它們的同步和內存使用。 –

+0

@Minging Duck-理想情況下,你會把它包裝在自己的課堂上,這樣你就不會讓兩個人失去同步。是的,有更多的內存使用,雖然它只是一個不變的因素比只有一個結構。 – templatetypedef

+0

@templatetypedef:+1,但斐波那契堆而不是二進制堆(或nary-heap) - 真的嗎?我明白,理論上的攤銷範圍可能會更好,但實際情況是這樣嗎?參見,例如:http://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently。另外,對於某些操作,Fibonaaci堆實際上是否具有較差的最差情況複雜度? –

2

創建一個heap structure(用於第二個項目符號)並將其每個節點放置在一張地圖中(對於第一個項目符號)。

編輯: 最小堆的實現我做了一段時間,在過去的

#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

你也可以使用'std :: priority_queue'。 – Dawson

+0

@Toolbox堆結構是實現priority_queue的一種方式:) –

+0

我知道 - 我的意思是不需要重新實現已經是標準C++的一部分。 – Dawson

2

的boost :: bimap的可以做你想做的,在反向映射用於實現#2。

+0

如果多個密鑰的值相同,該怎麼辦? – templatetypedef

+0

@templatetypedef:你的選擇,可能有幾個索引,比如'bimap >'。 –

0

我覺得bimap的是

+0

如果多個鍵具有與它們相關的相同值,該怎麼辦? – templatetypedef

1

根據我的C++ 0x標準,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.

所以只需使用一張地圖。隨機查找是O(log(n)),獲得最高元素需要O(1)次。

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

這是哈希映射嗎?那麼查找也是O(1) – user875367

+0

不,哈希是無序的,所以你找不到最高的元素。 –