Есть ли стабильная куча?

Существует ли структура данных очереди с приоритетами, которая поддерживает следующие операции?

• Вставить (x, p) : добавить новую запись x с приоритетом p
• StableExtractMin () : возвращает и удаляет запись с минимальным приоритетом, разрывая связи по порядку вставки .

Таким образом, после вставки (a, 1), вставки (b, 2), вставки (c, 1), вставки (d, 2) последовательность StableExtractMin's вернет a, затем c, затем b, затем d.

Очевидно, что можно использовать любую структуру данных очереди приоритетов, сохранив пару в качестве фактического приоритета, но меня интересуют структуры данных, которые явно не хранят время вставки (или порядок вставки), по аналогии со стабильной сортировкой. ,$(p, time)$

Эквивалентно (?): Существует ли стабильная версия heapsort, которая не требует дополнительного пространства?$\Omega(n)$

Метод Bently-Saxe дает довольно естественную стабильную очередь с приоритетами.

Сохраните ваши данные в последовательности отсортированных массивов . имеет размер . Каждый массив также поддерживает счетчик . Записи массива содержат данные.$A_0,\ldots,A_k$$A_i$$2^i$$c_i$$A_i[c_i],\ldots,A_i[2^i-1]$

Для каждого все элементы в были добавлены более недавно, чем элементы в и внутри каждого элемента упорядочены по значению с разрывами связей путем размещения более старых элементов перед новыми элементами. Обратите внимание, что это означает, что мы можем объединить и и сохранить этот порядок. (В случае связей во время слияния возьмите элемент из .)$i$$A_i$$A_{i+1}$$A_i$$A_i$$A_{i+1}$$A_{i+1}$

Чтобы вставить значение , найдите наименьшее такое, что содержит 0 элементов, объедините и , сохраните его в и установите соответственно .$x$$i$$A_i$$A_0,\ldots,A_{i-1}$$x$$A_i$$c_0,\ldots,c_i$

Чтобы извлечь минимум, найдите самый большой индекс такой, что первый элемент в является минимальным по всем и с приращением .$i$$A_i[c_i]$$i$$c_i$

По стандартному аргументу это дает амортизированное время на операцию и является стабильным из-за порядка, описанного выше.$O(\log n)$

Для последовательности из вставок и извлечений здесь используются записей массива (не храните пустые массивы) плюс слов бухгалтерских данных. Он не отвечает на версию вопроса Михая, но показывает, что стабильное ограничение не требует много места. В частности, это показывает, что не существует нижней границы необходимого дополнительного пространства.$n$$n$$O(\log n)$$\Omega(n)$

Обновление: Рольф Фагерберг указывает, что если мы можем хранить нулевые (не данные) значения, то вся эта структура данных может быть упакована в массив размером , где - это количество вставок до сих пор.$n$$n$

Во-первых, обратите внимание, что мы можем упаковать в массив в указанном порядке ( сначала , затем если он не пустой, и т. Д.). Структура этого полностью закодирована двоичным представлением , количество элементов, вставленных до сих пор. Если двоичное представление имеет 1 в позиции , то будет занимать расположение массива, в противном случае оно не будет занимать расположения массива.$A_k,\ldots,A_0$$A_k$$A_{k-1}$$n$$n$$i$$A_i$$2^i$

При вставке и длины нашего массива увеличивайте на 1, и мы можем объединить плюс новый элемент, используя существующие на месте алгоритмы стабильного объединения.$n$$A_0,\ldots,A_i$

Теперь, где мы используем нулевые значения, мы избавляемся от счетчиков . В мы сохраняем первое значение, за которым нулевые значения , за которыми следуют оставшиеся значения. В течение минуты извлечения мы все еще можем найти значение, которое нужно извлечь за время , изучив . Когда мы находим это значение в мы устанавливаем в нуль, а затем выполняем двоичный поиск по чтобы найти первое ненулевое значение и поменять местами и .$c_i$$A_i$$c_i$$2^i-c_i-1$$O(\log n)$$A_0[0],\ldots,A_k[0]$$A_i[0]$$A_i[0]$$A_i$$A_i[c_i]$$A_i[0]$$A_i[c_i]$

Конечный результат: вся структура может быть реализована с одним массивом, длина которого увеличивается с каждой вставкой, и одним счетчиком , который подсчитывает количество вставок.$n$

Я не уверен, каковы ваши ограничения; соответствует ли следующее? Храните данные в массиве, который мы интерпретируем как неявное двоичное дерево (например, двоичная куча), но с элементами данных на нижнем уровне дерева, а не на его внутренних узлах. Каждый внутренний узел дерева хранит меньшее из значений, скопированных из его двух дочерних элементов; в случае галстуков, скопируйте левого ребенка.

Чтобы найти минимум, посмотрите на корень дерева.

Чтобы удалить элемент, пометьте его как удаленный (отложенное удаление) и распространите вверх по дереву (каждый узел на пути к корню, содержащий копию удаленного элемента, должен быть заменен копией другого дочернего элемента). Сохраняйте количество удаленных элементов и, если он когда-либо станет слишком большим, доля всех элементов перестроит структуру, сохранив порядок элементов на нижнем уровне - перестройка занимает линейное время, поэтому эта часть добавляет только постоянное амортизированное время к сложность операции.

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

Это не ответ на более строгую версию вопроса Михая, потому что он использует вдвое больше памяти, чем истинная неявная структура данных, даже если мы проигнорируем затраты на обработку ленивой обработки.

Является ли следующее правильное толкование вашей проблемы:

Вы должны хранить N ключей в массиве A [1..N] без вспомогательной информации, которую вы можете поддерживать: * insert key * delete min, которая выбирает самый ранний вставленный элемент, если есть несколько минимумов

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

Интересный.

Краткий ответ: вы не можете.

Чуть дольше отвечу:

Вам понадобится дополнительное место для хранения «возраста» вашей записи, что позволит вам различать идентичные приоритеты. И вам понадобится место для информации, которая позволит быстро вставлять и извлекать. Плюс ваша полезная нагрузка (значение и приоритет).$\Omega(n)$$\Omega(n)$

И для каждой полезной нагрузки, которую вы храните, вы сможете «скрыть» некоторую информацию в адресе (например, означает, что Y старше X). Но в этой «скрытой» информации вы либо скрыте «возраст», либо ИЛИ «быстрый поиск» информации. Не оба.$addr(X) < addr(Y)$

Очень длинный ответ с неточной ложной математикой:

Примечание: самый конец второй части отрывочен, как уже упоминалось. Если бы какой-нибудь математик мог предоставить лучшую версию, я был бы благодарен.

Давайте подумаем о количестве данных, которые задействованы на X-битной машине (скажем, 32- или 64-битной), с шириной записей (значение и приоритет) машинных слов.$P$

У вас есть набор потенциальных записей, которые частично упорядочены: и но вы не можете сравнить и .$(a,1) < (a,2)$$(a,1) = (a,1)$$(a,1)$$(b,1)$

Однако вы хотите иметь возможность сравнивать два несопоставимых значения из вашего набора записей на основе того, когда они были вставлены. Так что у вас есть здесь еще один набор значений: те , которые были вставлены, и вы хотите повысить его с помощью частичного порядка: тогда и только тогда был вставлен перед .$X < Y$$X$$Y$

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

• Время вставки (относительно других записей, все еще находящихся в структуре) требует битов информации (с полезной нагрузкой P-байтов и доступных байтов памяти).$X - log_2(P)$$2^X$
• Полезная нагрузка (значение и приоритет вашей записи) требует машинных слов информации.$P$

Это означает, что вы должны каким-то образом хранить дополнительные биты информации для каждой сохраняемой вами записи. И это для записей.$X - log_2(P)$$O(n)$$n$

Теперь, сколько бит информации каждая ячейка памяти предоставляет нам?

• $W$ бит данных ( - ширина слова машины).$W$
• $X$ бит адреса.

Теперь предположим, что (полезная нагрузка имеет ширину хотя бы одного машинного слова (обычно один октет)). Это означает, что , поэтому мы можем разместить информацию о порядке вставки в адресе ячейки. Вот что происходит в стеке: ячейки с наименьшим адресом поступают в стек первыми (и выходят последними).$P \geq 1$$X - log_2(P) < X$

Итак, для хранения всей нашей информации у нас есть две возможности:

• Сохраните порядок вставки в адресе, а данные - в памяти.
• Сохраните оба в памяти и оставьте адрес свободным для другого использования.

Очевидно, чтобы избежать потерь, мы будем использовать первое решение.

Теперь для операций. Я полагаю, вы хотите иметь:

• $Insert(task, priority)$ с сложностью по времени.$O(log n)$
• $StableExtractMin()$ с сложностью по времени.$O(log n)$

Давайте посмотрим на :$StableExtractMin()$

Действительно действительно общий алгоритм выглядит так:

1. Найдите запись с минимальным приоритетом и минимальным «временем вставки» в .$O(log n)$
2. Удалите его из структуры в .$O(log n)$
3. Верни это.

Например, в случае с кучей, она будет немного по-другому организована, но работа такая же: 1. Найдите минимальную запись в 2. Удалите ее из структуры в 3. Исправьте все так, чтобы в следующий раз # 1 и # 2 все еще были то есть "восстановить кучу". Это нужно сделать в «O (log n)» 4. Вернуть элемент.$0(1)$$O(1)$$O(1)$

Возвращаясь к общему алгоритму, мы видим, что, чтобы найти запись за , нам нужен быстрый способ выбрать правильный из кандидатов (в худшем случае, память полный).$O(log n)$$2^(X - log_2(P))$

Это означает, что нам нужно хранить битов информации для извлечения этого элемента (каждый бит делит пополам пространство-кандидат, поэтому у нас есть делений, что означает сложность времени).$X - log_2(P)$$O(log n)$$O(log n)$

Эти биты информации могут быть сохранены как адрес элемента (в куче, минимальное значение находится на фиксированном адресе), или, например, с указателями (в двоичном дереве поиска (с указателями)), вы должны следовать в среднем чтобы добраться до мин).$O(log n)$

Теперь, при удалении этого элемента, нам нужно увеличить следующую запись min, чтобы в ней было правильное количество информации, чтобы в следующий раз разрешить поиск , то есть, так как у него есть битов информация, отличающая его от других кандидатов.$O(log n)$$X - log_2(P)$

То есть, если у вас недостаточно информации, вам нужно добавить ее. В (несбалансированном) бинарном дереве поиска информация уже есть: вам придется поместить NULL-указатель куда-нибудь, чтобы удалить элемент, и без каких-либо дальнейших операций BST будет доступен для поиска за времени на средний.$O(log n)$

После этого, это немного отрывочно, я не уверен, как это сформулировать. Но у меня есть сильное чувство, что каждый из оставшихся элементов в вашем наборе должен будет иметь биты информации, которые помогут найти следующую минуту и ​​дополнить ее достаточным количеством информации, чтобы ее можно было найти в время в следующий раз.O ( l o g n $X - log_2(P)$$O(log n)$

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

Теперь это означает, что нам нужно хранить больше битов информации для каждого элемента. Итак, для каждого элемента имеем:$X - log_2(P)$

• Время вставки, бит.$X - log_2(P)$
• Полезная нагрузка машинных слов.$P$
• Информация «быстрого поиска», бит.$X - log_2(P)$

Поскольку мы уже используем содержимое памяти для хранения полезной нагрузки и адрес для хранения времени вставки, у нас не осталось места для хранения информации «быстрого поиска». Таким образом, нам придется выделить дополнительное пространство для каждого элемента, и таким образом «тратить» дополнительное пространство.$\Omega(n)$

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

Я не думаю, что это возможно

конкретный случай:

       x
    x    x
  x  x  1  x
1  x  

мин куча со всеми х> 1

в конечном итоге, что-то даст выбор

       x
    1    1
  x  x  x  x
x  x  

Теперь, какой 1 распространять в корень?