Очередь приоритетов с приоритетами динамических позиций

Ответ 1

Я бы предложил сначала попробовать подход "вживую", чтобы обновить приоритет:

• удалить элемент из очереди
• повторно вставьте его с новым приоритетом

В С++ это можно сделать с помощью 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);
  }
}

Ответ 2

Приоритетные очереди, такие как обычно, реализуются с использованием структуры данных двоичной кучи, как было предложено другим пользователем, которая обычно представляется с использованием массива, но также может использовать двоичное дерево. На самом деле нетрудно увеличить или уменьшить приоритет элемента в куче. Если вы знаете, что вы изменяете приоритет многих элементов перед тем, как следующий элемент выскочит из очереди, вы можете временно отключить динамическое переупорядочение, вставить все элементы в конце кучи и затем изменить порядок всей кучи (за счет стоимости O (n)) непосредственно перед тем, как элемент нужно выскочить. Важная вещь о кучках заключается в том, что он стоит только O (n), чтобы поместить массив в порядок кучи, но O (n log n), чтобы отсортировать его.

Я успешно использовал этот подход в большом проекте с динамическими приоритетами.

Вот моя реализация параметризованной реализации очереди приоритетов на языке программирования Curl.

Ответ 3

Стандартная двоичная куча поддерживает 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.

Ответ 4

Google имеет для вас несколько ответов, включая реализацию один в Java.

Однако это звучит как что-то, что было бы проблемой домашней работы, поэтому, если это так, я предлагаю сначала попробовать сначала разобраться с идеями, а затем потенциально ссылаться на чужую реализацию, если вы где-нибудь застряли и нуждаетесь в указателе в в правильном направлении. Таким образом, вы менее склонны быть "предвзятыми" в отношении точного метода кодирования, используемого другим программистом, и с большей вероятностью понимаете, почему каждый фрагмент кода включен и как он работает. Иногда это может быть слишком заманчиво, чтобы сделать перефразирующий эквивалент "копировать и вставлять".

Ответ 5

Я ищу именно то же самое!

И вот некоторые из моих идей:

• Поскольку приоритет элемента постоянно меняется, это бессмысленно сортировать очередь перед извлечением элемента.
• Итак, мы должны забыть использовать приоритетную очередь. И "частично" сортировать контейнер при извлечении элемента.

И выберите из следующих алгоритмов сортировки STL:  а. раздел  б. stable_partition  с. nth_element  д. partial_sort  е. partial_sort_copy  е. Сортировать  г. stable_sort

stable_partition и nth_element - алгоритмы сортировки по линейному времени, которые должны быть нашими 1-м выбором.

НО, похоже, что в официальной библиотеке Java нет этих алгоритмов. В результате я предлагаю вам использовать java.util.Collections.max/min, чтобы делать то, что вы хотите.