Клавиша увеличения и уменьшения ключа в двоичной min-heap

16

Во многих обсуждениях двоичной кучи в качестве поддерживаемой операции для минимальной кучи обычно указывается только ключ уменьшения. Например, глава 6.1 CLR и эта страница википедии . Почему ключ увеличения обычно не указывается для min-heap? Я полагаю, что это можно сделать в O (высота), итеративно меняя увеличенный элемент (x) на минимум его дочерних элементов, пока ни один из его дочерних элементов не станет больше, чем x.

например

IncreaseKey(int pos, int newValue)
{
   heap[pos] = newValue;
   while(left(pos) < heap.Length)
   {
      int smallest = left(pos);
      if(heap[right(pos)] < heap[left(pos)])
         smallest = right(pos);
      if(heap[pos] < heap[smallest])
      { 
         swap(smallest, pos);
         pos= smallest;
      }
      else return;
   }   
}

Это правильно? Если нет, то почему? Если да, почему ключ увеличения не указан для минимальной кучи?

GatotPujo
источник
1
Прочитав все ответы, я бы сказал, что это странное упущение, вероятно, вызванное исторически первым использованием min-heap в алгоритме Дейкстры.
Маартин
3
Конечно, вы всегда можете реализовать клавишу увеличения, используя удаление с последующей вставкой, а само удаление можно реализовать как клавишу уменьшения (до -∞), за которой следует delete-min.
Давмак
Комментарий @maaartinus - правильный ответ.
максимум

Ответы:

6

Алгоритм, который вы предлагаете, просто сложен. И действительно - если вы увеличите значение элемента в минимальной куче, а затем сложите его поддерево, то у вас получится легальная минимальная куча.

Shaull
источник
тогда почему CLR или Wikipedia не содержат список увеличения ключа, чтобы быть поддерживаемой операцией? Меня как-то ввели в заблуждение думать, что это невозможно в минимальной куче
GatotPujo
Я согласен, что это вводит в заблуждение, но я не вижу никакой ошибки в алгоритме.
Shaull
5

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

Двоичные кучи реализуют очередь приоритетов абстрактной структуры данных, которая запрашивает операции is_empty, add_element (ключ с его приоритетом), find_min и delete_min. Более сложные очереди также позволяют уменьшить приоритет ключа (в min_heap) или даже увеличить его. На самом деле, вы дали реализацию.

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

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

Хендрик Ян
источник
1
Спасибо за объяснение. Однако в CLR клавиша уменьшения также имеет положение в качестве узла в качестве параметра.
GatotPujo
Вы правы. Я не смог найти причину этой асимметрии в определении очередей приоритетов в разделе 6.5 CLRS. Примечание: ключ увеличения не используется в Heapsort, приложении этой главы. Кажется, асимметрия между увеличением и уменьшением связана только с тем, как структура данных используется, например, в алгоритме Дейкстры. Там (с использованием мини-кучи) некоторые выбранные узлы могут стать более срочными и перемещаться «вверх» в куче.
Хендрик Янв
0

Я думаю, что первое, что нужно рассмотреть, это что такое поддерживаемая операция?

Соответствует ли «вставка значения с определенным фиксированным ключом» (например, для ключей, взятых из целочисленной области, вставка с ключом = 3) поддерживаемой операцией для минимальной кучи?

Нет, потому что эту операцию можно легко реализовать с помощью более общих поддерживаемых операций. Аналогично, вставка 2 элементов одновременно может быть выполнена с помощью существующей insertоперации.

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

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

Имея это в виду, думаете ли вы, что ключ увеличения может быть реализован исключительно с другими поддерживаемыми операциями, без потери производительности? Если это так, то это не поддерживаемая операция по вышеприведенному определению, в противном случае вы вполне можете быть правы.

Возможно, определение поддерживаемой операции, которую я предоставляю, является моим, насколько я знаю. Это не формально и, следовательно, подлежит обсуждению (хотя мне это кажется довольно понятным). Тем не менее, я был бы рад, если бы кто-то мог предоставить источник, который четко и однозначно определит, что является поддерживаемой операцией для типов данных, или, по крайней мере, определит ее лучше, чем моя (это определение дано в CLR? У меня нет копии) ).

Мое второе замечание будет касаться того, как мы определяем приоритетную очередь (смысл существования двоичных куч). Является ли increase_keyнеобходимая операция для этого типа данных, то есть для его правильного использования?

Как вы видите, мой угол - все о определениях. На самом деле я не даю ответ на ваши вопросы, просто некоторые указатели, поэтому улучшения приветствуются.

didierc
источник
1
Пример использования может быть, если я хочу сохранить приоритетную очередь объекта на основе наименее недавно использованных объектов (например, чтобы я мог легко удалить наименее недавно использованные объекты). Я могу использовать минимальную кучу с последней датой доступа в качестве ключа. Если к объекту обращаются, его ключ нужно будет увеличить.
GatotPujo
Очень хороший момент. Кажется, моя точка зрения немного ограничена. Действительно, ответ @HendrikJan дает очень хорошее объяснение.
Didierc