Hàng đợi ưu tiên với các ưu tiên mục động

Question

Tôi cần triển khai hàng đợi ưu tiên trong đó mức độ ưu tiên của một mục trong hàng đợi có thể thay đổi và hàng đợi tự điều chỉnh sao cho các mục luôn bị xóa theo đúng thứ tự. Tôi có một số ý tưởng về cách tôi có thể thực hiện điều này nhưng tôi chắc chắn đây là một cấu trúc dữ liệu khá phổ biến vì vậy tôi hy vọng tôi có thể sử dụng một cách thực hiện bởi một ai đó thông minh hơn tôi làm cơ sở.

Mọi người có thể cho tôi biết tên của loại hàng đợi ưu tiên này để tôi biết tìm kiếm gì hay thậm chí tốt hơn, chỉ cho tôi biết cách triển khai?

Answer 1

tôi sẽ đề nghị đầu tiên cố gắng tiếp cận đầu-in, cập nhật một ưu tiên:

• xóa các mục từ hàng đợi
• tái chèn nó với các ưu tiên mới

Trong C++, điều này có thể được thực hiện bằng cách sử dụng một std::multi_map, điều quan trọng là đối tượng phải nhớ nơi nó được lưu trữ trong cấu trúc để có thể xóa chính nó một cách hiệu quả. Để chèn lại, rất khó vì bạn không thể đoán bạn biết gì về các ưu tiên.

class Item; 

typedef std::multi_map<int, Item*> priority_queue; 

class Item 
{ 
public: 
    void add(priority_queue& queue); 
    void remove(); 

    int getPriority() const; 
    void setPriority(int priority); 

    std::string& accessData(); 
    const std::string& getData() const; 

private: 
    int mPriority; 
    std::string mData; 

    priority_queue* mQueue; 
    priority_queue::iterator mIterator; 
}; 

void Item::add(priority_queue& queue) 
{ 
    mQueue = &queue; 
    mIterator = queue.insert(std::make_pair(mPriority,this)); 
} 

void Item::remove() 
{ 
    mQueue.erase(mIterator); 
    mQueue = 0; 
    mIterator = priority_queue::iterator(); 
} 

void Item::setPriority(int priority) 
{ 
    mPriority = priority; 
    if (mQueue) 
    { 
    priority_queue& queue = *mQueue; 
    this->remove(); 
    this->add(queue); 
    } 
} 

Answer 2

Google has a number of answers cho bạn, bao gồm cả việc triển khai one in Java. Tuy nhiên, điều này nghe giống như một vấn đề về bài tập ở nhà, vì vậy nếu tôi muốn, bạn nên cố gắng tự mình thực hiện ý tưởng trước, sau đó có khả năng tham khảo cách thực hiện của người khác nếu bạn gặp khó khăn ở đâu đó và cần một con trỏ đi đúng hướng. Bằng cách đó, bạn ít có khả năng bị "thiên vị" đối với phương pháp mã hóa chính xác được sử dụng bởi lập trình viên khác và có nhiều khả năng hiểu tại sao mỗi đoạn mã được bao gồm và cách hoạt động của mã. Đôi khi nó có thể là một chút quá hấp dẫn để làm tương đương diễn giải của "sao chép và dán".

Answer 3

Một đống nhị phân tiêu chuẩn hỗ trợ 5 hoạt động (ví dụ dưới đây giả định một đống max):

* find-max: return the maximum node of the heap 
* delete-max: removing the root node of the heap 
* increase-key: updating a key within the heap 
* insert: adding a new key to the heap 
* merge: joining two heaps to form a valid new heap containing all the elements of both. 

Như bạn có thể thấy, trong một đống tối đa, bạn có thể tăng một phím bất kỳ. Trong heap tối thiểu bạn có thể giảm một khóa tùy ý. Bạn không thể thay đổi phím cả hai cách không may, nhưng điều này sẽ làm gì? Nếu bạn cần thay đổi cả hai cách, bạn có thể muốn suy nghĩ về việc sử dụng một số min-max-heap.

Answer 4

Tôi đang tìm kiếm chính xác điều tương tự!

Và đây là một số ý tưởng của tôi:

1. Từ một ưu tiên của một mục tiếp tục thay đổi, đó là vô nghĩa để sắp xếp hàng đợi trước khi lấy một mục.
2. Vì vậy, chúng ta nên quên sử dụng hàng đợi ưu tiên. Và "một phần" sắp xếp vùng chứa trong khi truy xuất một mục.

Và chọn từ các thuật toán sắp xếp STL sau: a. phân vùng b. stable_partition c. nth_element d. partial_sort e. partial_sort_copy f. sắp xếp g.stable_sort

phân vùng, stable_partition và nth_element là các thuật toán sắp xếp theo thời gian tuyến tính, đây phải là lựa chọn thứ nhất của chúng tôi.

NHƯNG, có vẻ như không có các thuật toán được cung cấp trong thư viện Java chính thức. Kết quả là, tôi sẽ đề nghị bạn sử dụng java.util.Collections.max/min để làm những gì bạn muốn.

Answer 5

Hàng đợi ưu tiên như thế này thường được triển khai bằng cấu trúc dữ liệu heap nhị phân như một người khác được đề xuất, thường được biểu diễn bằng mảng nhưng cũng có thể sử dụng cây nhị phân. Nó thực sự không khó để tăng hoặc giảm mức ưu tiên của một phần tử trong heap. Nếu bạn biết bạn đang thay đổi mức độ ưu tiên của nhiều phần tử trước khi phần tử tiếp theo xuất hiện từ hàng đợi, bạn có thể tạm thời tắt sắp xếp lại động, chèn tất cả các phần tử vào cuối heap và sau đó sắp xếp lại toàn bộ đống (với chi phí của O (n)) ngay trước khi phần tử cần được xuất hiện. Điều quan trọng về heaps là nó chỉ tốn O (n) để đặt một mảng vào thứ tự heap nhưng O (n log n) để sắp xếp nó.

Tôi đã sử dụng phương pháp này thành công trong một dự án lớn với các ưu tiên động.

Đây là triển khai của tôi về tham số priority queue implementation in the Curl programming language.