C++ điển ưu tiên

Question

Tôi cần một container để lưu trữ cặp, tôi có hai hoạt động:

1. cập nhật giá trị bằng phím
2. lấy chìa khóa có giá trị tối đa.

Đối với hoạt động đầu tiên, bản đồ là cấu trúc tốt. Đối với hoạt động thứ hai, có vẻ hàng đợi ưu tiên là hàng đợi ưu tiên. Bạn sẽ làm điều này như thế nào? Có anyway để có cả hai hoạt động được thực hiện mà không có một vòng lặp O (n)? Cảm ơn.

Answer 1

Một giải pháp hiệu quả để tiệm này sẽ được sử dụng một sự kết hợp của một bảng băm và một đống Fibonacci. Bạn sẽ sử dụng bảng băm để có thể truy cập giá trị được liên kết với bất kỳ khóa cụ thể nào trong thời gian O (1) và sẽ sử dụng vùng Fibonacci để có thể nhanh chóng tìm cặp khóa/giá trị có giá trị thấp nhất (làm như vậy trong O (1)).

Nếu bạn muốn thay đổi giá trị liên quan đến khóa, nếu bạn tăng giá trị, bạn có thể làm như vậy trong (được phân bổ) O (1) thời gian bằng cách sử dụng thao tác tăng khóa trên vùng Fibonacci, O (1) thời gian khấu hao. Nếu bạn đang giảm giá trị, nó sẽ mất thời gian O (log n) để xóa phần tử ra khỏi vùng Fibonacci và sau đó chèn lại nó.

Nhìn chung, điều này mang lại một độ phức tạp thời gian của

• Chèn một yếu tố mới: O (1) cho băm, O (1) nhằm chèn vào Fibonacci đống: O (1) thời gian.
• Xóa phần tử: O (1) cho hàm băm, O (log n) để xóa khỏi vùng Fibonacci: O (log n) time.
• Tìm phần tử trên cùng: O (1) để tra cứu trong vùng Fibonacci: O (1) lần.
• Tăng giá trị: O (1) cho hàm băm, O (1) để tăng khóa: O (1) lần.
• Giảm giá trị: O (1) cho băm, O (nhật ký n) để xóa/chèn: O (nhật ký n).

Hy vọng điều này sẽ hữu ích!

Answer 2

Tạo heap structure (đối với dấu đầu dòng thứ hai) và đặt từng nút trong bản đồ (đối với dấu đầu dòng).

EDIT: An thực hiện đống min Chúng tôi đã thực hiện một số thời gian trong

#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

tăng quá khứ :: bimap có thể làm những gì bạn muốn, nơi mà các bản đồ ngược được sử dụng để thực hiện # 2.

Answer 4

Tôi nghĩ rằng bimap là con đường tốt nhất

Answer 5

Theo C++ 0x tôi chuẩn, 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.

Vì vậy, chỉ cần sử dụng một bản đồ. Tra cứu ngẫu nhiên là O (log (n)), và để lấy phần tử cao nhất có thời gian O (1).

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