Во многих обсуждениях двоичной кучи в качестве поддерживаемой операции для минимальной кучи обычно указывается только ключ уменьшения. Например, глава 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;
}
}
Это правильно? Если нет, то почему? Если да, почему ключ увеличения не указан для минимальной кучи?
algorithms
data-structures
heaps
priority-queues
GatotPujo
источник
источник
Ответы:
Алгоритм, который вы предлагаете, просто сложен. И действительно - если вы увеличите значение элемента в минимальной куче, а затем сложите его поддерево, то у вас получится легальная минимальная куча.
источник
Причина, по которой ваша операция не указана в списке, заключается в том, что вы не просто заинтересованы во всех операциях, которые могут быть легко реализованы с использованием определенной структуры данных, а скорее другим способом. Учитывая набор операций, каков наиболее эффективный способ (с точки зрения пространства и времени) для реализации этих операций. (Но я добавлю больше к этому позже)
Двоичные кучи реализуют очередь приоритетов абстрактной структуры данных, которая запрашивает операции is_empty, add_element (ключ с его приоритетом), find_min и delete_min. Более сложные очереди также позволяют уменьшить приоритет ключа (в min_heap) или даже увеличить его. На самом деле, вы дали реализацию.
Два замечания. Ваша операция используется в функции heapify, которая эффективно создает кучу из массива. В heapify ваша операция повторяется (начиная с последнего ключа).
Тогда, самое главное, ваш код использует положение узла. Для очереди с чистой структурой данных, которая обманывает. Эта структура данных запрашивает выполнение определенной операции с заданным ключом. Таким образом, чтобы уменьшить или увеличить приоритет элемента, вам сначала нужно его найти. Я думаю, что это главная причина, по которой он не указан.
источник
Я думаю, что первое, что нужно рассмотреть, это что такое поддерживаемая операция?
Соответствует ли «вставка значения с определенным фиксированным ключом» (например, для ключей, взятых из целочисленной области, вставка с ключом = 3) поддерживаемой операцией для минимальной кучи?
Нет, потому что эту операцию можно легко реализовать с помощью более общих поддерживаемых операций. Аналогично, вставка 2 элементов одновременно может быть выполнена с помощью существующей
insertоперации.С другой стороны,
insertоперация не может быть определена иначе, как путем раскрытия деталей реализации. Это почти то же самое для операций, перечисленных на странице википедии, заheapifyисключением, что может быть реализовано с помощью последовательностиinsert.Другими словами, для типа предусмотрены элементарные операции, которые тесно связаны с деталями реализации, чтобы они хорошо выполнялись, и есть другие операции, которые не соответствуют этому правилу и, следовательно, могут быть реализованы как комбинации из канонических.
Имея это в виду, думаете ли вы, что ключ увеличения может быть реализован исключительно с другими поддерживаемыми операциями, без потери производительности? Если это так, то это не поддерживаемая операция по вышеприведенному определению, в противном случае вы вполне можете быть правы.
Возможно, определение поддерживаемой операции, которую я предоставляю, является моим, насколько я знаю. Это не формально и, следовательно, подлежит обсуждению (хотя мне это кажется довольно понятным). Тем не менее, я был бы рад, если бы кто-то мог предоставить источник, который четко и однозначно определит, что является поддерживаемой операцией для типов данных, или, по крайней мере, определит ее лучше, чем моя (это определение дано в CLR? У меня нет копии) ).
Мое второе замечание будет касаться того, как мы определяем приоритетную очередь (смысл существования двоичных куч). Является ли
increase_keyнеобходимая операция для этого типа данных, то есть для его правильного использования?Как вы видите, мой угол - все о определениях. На самом деле я не даю ответ на ваши вопросы, просто некоторые указатели, поэтому улучшения приветствуются.
источник