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

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

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

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

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

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

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

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

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

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

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

Нашел решение («разница» означает «приоритет» в коде, а 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){
    }
};

1. построить очередь на основе максимального числа (корень самый большой)
2. пока он не заполнится, заполните как обычно
3. когда он заполнен, для каждого нового элемента
   1. Проверить, не меньше ли новый элемент корня.
   2. , если он больше или равен корню, отклонить.
   3. в противном случае замените root на новый элемент и выполните обычное «просеивание» кучи.

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

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

P.S. Очевидно, программирование без сна - не лучшая идея.

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

int left = i / 2;

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

int right = left + 1;