Приоритетная очередь с ограниченным пространством: поиск хорошего алгоритма

Ответ 1

Навалочные массивы кажутся идеальными для вашей цели. Я не уверен, почему вы их отклонили.

Вы используете максимальную кучу.

Скажем, у вас есть куча элементов (реализована как массив), которая содержит N наименьших элементов, которые были просмотрены до сих пор.

Когда элемент входит, вы проверяете максимальное время (O (1)) и отклоняете, если оно больше.

Если значение, приходящее ниже, измените корень на новое значение и просеите это измененное значение - наихудшее время O (log N).

Процесс sift-down прост: начиная с root, на каждом шаге вы обмениваете это значение с ним большим дочерним до тех пор, пока свойство max-heap не будет восстановлено.

Таким образом, вам не придется делать никаких удалений, которые вам, вероятно, понадобятся, если вы используете std:: priority_queue. В зависимости от реализации std:: priority_queue это может привести к выделению/освобождению памяти.

Таким образом, вы можете получить код следующим образом:

• Выделенный массив размера N.
• Заполните его с помощью первых N элементов, которые вы видите.
• heapify (вы должны найти это в стандартных текстовых книгах, он использует sift-down). Это O (N).
• Теперь любой новый элемент, который вы получаете, вы либо отклоняете его в O (1), либо вставляете путем отсеивания в худшем случае O (logN).

В среднем, однако, вам, вероятно, не придется просеивать новое значение до конца и может стать лучше среднего времени вставки вставки (хотя я и не пробовал это доказать).

Вы выделяете массив размера N только один раз, и любая вставка выполняется путем обмена элементами массива, поэтому после этого не происходит динамического выделения памяти.

Проверьте страницу вики, в которой есть псевдокод для heapify и sift-down: http://en.wikipedia.org/wiki/Heapsort

Ответ 2

Используйте std::priority_queue с самым большим элементом в голове. Для каждого нового элемента отбросьте его, если это >= головной элемент, иначе поместите элемент головы и вставьте новый элемент.

Боковое примечание. Стандартные контейнеры будут расти только в том случае, если вы их вырастут. Пока вы удаляете один элемент перед вставкой нового элемента (конечно, если он достигнет максимального размера), этого не произойдет.

Ответ 3

Большинство приоритетных очередей, на которых я работаю, основаны на связанных списках. Если у вас есть предопределенное количество уровней приоритета, вы можете легко создать очередь приоритетов с вставкой O (1), имея массив связанных списков - один связанный список на уровень приоритета. Предметы того же приоритета, разумеется, вырождаются в FIFO, но это можно считать приемлемым.

Добавление и удаление затем становится чем-то вроде (ваш API может меняться)...

listItemAdd (&list[priLevel], &item);      /* Add to tail */
pItem = listItemRemove (&list[priLevel]);  /* Remove from head */

Получение первого элемента в очереди становится проблемой поиска непустого связанного списка с наивысшим приоритетом. Это может быть O (N), но есть несколько трюков, которые вы можете использовать для ускорения.

• В структуре очереди приоритетов держите указатель или индекс или что-то в связанном списке с текущим приоритетом. Это нужно обновлять каждый раз, когда элемент добавляется или удаляется из очереди приоритетов.
• Используйте растровое изображение, чтобы указать, какие связанные списки не пустые. В сочетании с поиском наиболее значимого бита или поиском алгоритма с наименьшим значащим битом вы обычно можете тестировать до 32 списков одновременно. Опять же, это нужно будет обновить при каждом добавлении/удалении.

Надеюсь, что это поможет.

Ответ 4

Если количество приоритетов невелико и фиксировано, вы можете использовать кольцевой буфер для каждого приоритета. Это приведет к расточительству пространства, если объекты большие, но если их размер сравним с указателем/индексом, чем варианты с сохранением дополнительных указателей в объектах, таким же образом может увеличить размер массива.
Или вы можете использовать простой односвязный список внутри массива и хранить указатели/индексы 2 * M + 1, один указывает на первый свободный node, а другие пары будут указывать на голову и хвост каждого приоритета. В этом случае вам придется сравнивать в средстве avg. O (M), прежде чем вывести следующий node с O (1). И вставка будет принимать O (1).

Ответ 5

Если вы создаете приоритетную очередь STL с максимальным размером (возможно, из вектора, инициализированного заполнителями), а затем проверяете размер перед вставкой (удаляя элемент, если необходимо заранее), вы никогда не будете иметь динамическое распределение во время операций вставки. Реализация STL довольно эффективна.

Ответ 6

"Вопросы вычислительной техники" см. стр. 158. Сама реализация очень хорошо, и вы можете даже немного ее настроить, не делая ее менее читаемой. Например, когда вы вычисляете левый дочерний элемент:

int left = i / 2;

Вы можете вычислить правую кнопку следующим образом:

int right = left + 1;

Ответ 7

Найдено решение ( "разница" означает "приоритет" в коде, а maxRememberedResults - 255 (может быть любым (2 ^ n - 1)):

template <typename T> inline void swap(T& a, T& b){
    T c = a;
    a = b;
    b = c;
}


struct MinDifferenceArray{
    enum{maxSize = maxRememberedResults};
    int size;
    DifferenceData data[maxSize];
    void add(const DifferenceData& val){
        if (size >= maxSize){
            if(data[0].difference <= val.difference)
                return;

            data[0] = val;

            for (int i = 0; (2*i+1) < maxSize; ){
                int next = 2*i + 1;
                if (data[next].difference < data[next+1].difference)
                    next++;
                if (data[i].difference < data[next].difference)
                    swap(data[i], data[next]);
                else
                    break;
                i = next;
            }
        }
        else{
            data[size++] = val;
            for (int i = size - 1; i > 0;){
                int parent = (i-1)/2;
                if (data[parent].difference < data[i].difference){
                    swap(data[parent], data[i]);
                    i = parent;
                }
                else
                    break;
            }
        }
    }

    void clear(){
        size = 0;
    }

    MinDifferenceArray()
        :size(0){
    }
};

• создать максимальную очередь (корень самый большой)
• пока он не заполнится, заполните
• когда он заполнен, для каждого нового элемента
  • Убедитесь, что новый элемент меньше, чем root.
  • если он больше или равен root, отклоните.
  • в противном случае замените корень на новый элемент и выполните обычную кучу "sift-down".

И мы получаем O (log (N)) как худший сценарий.

Это то же самое решение, что и предоставленное пользователем с псевдонимом "Морон". Спасибо всем за ответы.

P.S. По-видимому, программирование без сна было неплохой идеей.