Приоритетная очередь с динамическими приоритетами объекта
Я должен реализовать приоритетную очередь, где приоритет объекта в очереди может измениться, и очередь корректирует себя так, чтобы объекты всегда удалялись в правильном порядке. У меня есть некоторые идеи того, как я мог реализовать это, но я уверен, что это - настоящая структура общих данных, таким образом, я надеюсь, что могу использовать реализацию кем-то более умным, чем я как основа.
Кто-либо может сказать мне название этого типа приоритетной очереди, таким образом, я знаю, что искать или, еще лучше, указать на меня на реализацию?
5 ответов
Я бы посоветовал сначала попробовать метод "заголовок", чтобы обновить приоритет:
- удалить элемент из очереди
- повторно вставить его с новым приоритетом
В C ++ это можно сделать с помощью std :: multi_map , важно то, что объект должен помнить, где он хранится в структуре, чтобы иметь возможность эффективно удалить себя . Для повторной вставки это сложно, поскольку вы не можете предполагать, что что-то знаете о приоритетах.
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);
}
}
Стандартная двоичная куча поддерживает 5 операций (в приведенном ниже примере предполагается максимальная куча):
* 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.
Как видите, в максимальной куче вы можете увеличить произвольную клавишу. В минимальной куче вы можете уменьшить произвольный ключ. К сожалению, вы не можете изменить ключи в обоих направлениях, но подойдет ли это? Если вам нужно изменить ключи в обоих направлениях, вы можете подумать об использовании min-max-heap .
У Google есть несколько ответов для вас, включая реализацию на Java .
Однако это звучит как проблема домашнего задания, поэтому, если это так, я бы посоветовал сначала попробовать проработать идеи самостоятельно, а затем потенциально сослаться на чью-то реализацию, если вы где-то застряли и вам понадобится указатель правильное направление. Таким образом, вы с меньшей вероятностью будете «склонны» к точному методу кодирования, используемому другим программистом, и с большей вероятностью поймете, почему включен каждый фрагмент кода и как он работает. Иногда бывает слишком заманчиво сделать перефразированный эквивалент «копировать и вставить».
Очереди приоритетов, подобные этой, обычно реализуются с помощью структуры данных двоичной кучи, как уже предлагал кто-то другой, которая обычно представлена с помощью массива, но может также использовать двоичное дерево. На самом деле несложно увеличить или уменьшить приоритет элемента в куче. Если вы знаете, что вам нужно изменить приоритет многих элементов до того, как следующий элемент будет извлечен из очереди, вы можете временно отключить динамическое переупорядочение, вставить все элементы в конец кучи, а затем переупорядочить всю кучу (с затратами O(n)) непосредственно перед тем, как элемент должен быть извлечен. Важным моментом в куче является то, что для приведения массива в порядок в куче требуется O(n), а для его сортировки - O(n log n).
Я успешно использовал этот подход в большом проекте с динамическими приоритетами.
Вот моя реализация параметризованной приоритетной очереди на языке программирования Curl.
Я ищу то же самое!
И вот кое-что из моей идеи:
- Поскольку приоритет элемента постоянно меняется, бессмысленно сортировать очередь перед получением элемента.
- Итак, мы должны забыть об использовании очереди с приоритетом. И «частично» сортировать контейнер при извлечении элемента.
И выберите один из следующих алгоритмов сортировки STL: a. раздел б. stable_partition c. nth_element d. partial_sort e. partial_sort_copy f. сортировать g. stable_sort
partition, stable_partition и nth_element - это алгоритмы линейной сортировки, которые должны быть нашим первым выбором.
НО, похоже, что этих алгоритмов нет в официальной библиотеке Java.В результате я предлагаю вам использовать java.util.Collections.max / min, чтобы делать то, что вы хотите.