Возможно ли реализовать двоичную кучу, которая является как максимальной, так и минимальной кучей?
Я пытаюсь реализовать двоичную кучу (очередь приоритетов), которая имеет возможности как минимальной, так и максимальной кучи. Это должно иметь insert(value), extractMin()и extractMax() метод. Методы извлечения удаляют значение из кучи и возвращают значение.
Я изначально использовал два массива, называемых minHeap а также maxHeapодин для хранения данных в структуре с минимальной кучей, а другой для хранения тех же данных в структуре с максимальной кучей. Поэтому, когда я звоню extractMin(), он удаляет и возвращает значение из minHeap, Затем я должен удалить это значение из maxHeap а также (и наоборот, если бы я позвонил extractMax()) для сохранения идентичного набора данных в обеих кучах. И из-за свойства порядка кучи гарантировано, что я найду это значение в листьях другой кучи. Поиск этого значения в другой куче приводит к временной сложности O (n) или, точнее, O (n / 2), так как я буду искать только листья. Не говоря уже о percolatingDown() а также percolatingUp() методы восстановления кучи после удаления значений уже O (log n); итого, методы извлечения были бы O (n). Проблема в том, что мне нужно, чтобы методы извлечения были O (log n).
Есть ли лучший способ сделать это?
Я также думал об этой идее, но хотел знать, что вы все думаете в первую очередь.
Я только что закончил кодировать «медианную кучу», поместив меньшую половину данных в максимальную кучу и большую половину в минимальную кучу. Благодаря этой структуре я могу легко получить медиану заданного набора значений. И я думал об использовании аналогичной структуры размещения меньшей половины данных в минимальной куче и большей половины в максимальной куче и использования среднего значения (а не медианы) всех значений в качестве решающего фактора того, поместить значение в максимальную или минимальную кучу при вызове insert(value), Я думаю, что это может сработать, так как методы извлечения останутся O (log n).
Решение
Простой способ — просто использовать двоичное дерево поиска, как рекомендует М. Шоу.
Если вам необходимо построить это поверх двоичных куч, то в каждой куче, рядом с каждым элементом, сохраните позицию элемента в другой куче. Каждый раз, когда вы перемещаете элемент в одну кучу, вы можете перейти прямо к его позиции в другой куче и обновить его. Когда вы выполняете delete-min или delete-max, дорогостоящее линейное сканирование в другой куче не требуется.
Например, если вы храните std::pairс first в качестве значения элемента и second поскольку позиция в другой куче, замена двух элементов в минимальной куче при обновлении их аналогов в максимальной куче может выглядеть следующим образом:
swap(minheap[i], minheap[j]);
maxheap[minheap[i].second].second = i;
maxheap[minheap[j].second].second = j;
Другие решения
Вы можете создать хеш-таблицу для элементов кучи, которая совместно используется двумя кучами. Таблица индексируется по значению элемента кучи. Значением хешированного сегмента может быть структура, состоящая из индекса массива в minHeap и maxHeap соответственно.
Преимущество этого подхода в том, что он не навязчивый, то есть структура элементов кучи остается неизменной. И вам не нужно создавать кучу бок о бок. Вы можете создавать один за другим с обычной процедурой создания кучи.
Например.,
struct tIndex
{
// Array index of the element in two heaps respectively
size_t minIndex;
size_t maxIndex;
};
std::unordered_map<int, tIndex> m;
Обратите внимание, что любое изменение в куче может изменить базовый индекс массива существующих элементов. Поэтому, когда вы добавляете / удаляете элемент или меняете местами два элемента, вам может потребоваться соответственно обновить его индекс массива в хеш-таблице.
Ты рядом. Хитрость заключается в использовании другого уровня косвенности. Храните ключи в массиве K [i] и храните только индексы i в кучах. Также держите две обратные карты: одну для максимальной кучи и одну для минимальной. Обратная карта — это массив целых чисел R, такой что R [i] — это местоположение в куче min (или max) индекса i для ключа K [i]. Другими словами, если M [j] — минимальная (или максимальная) куча, то R [M [j]] = j; Теперь, когда вы выполняете операцию просеивания для перемещения элементов в куче, вы должны одновременно обновлять соответствующую карту реверса. На самом деле это работает так же, как отношение выше. На каждом шаге, где вы меняете элемент кучи M [j] = z, также обновляйте обратную карту R [z] = j; Это увеличивает время выполнения только на небольшой постоянный коэффициент. Теперь, чтобы удалить K [i] из кучи, вы можете найти его за постоянное время: оно находится в M [R [i]]. Просейте это до корня и удалите это.
Я знаю, что это работает (поиск кучи объекта для удаления за постоянное время), потому что я реализовал его как часть более крупного алгоритма. Проверять, выписываться https://github.com/gene-ressler/lulu/blob/master/ext/lulu/pq.c . Большой алгоритм для объединения маркеров карты: https://github.com/gene-ressler/lulu/wiki
http://www.geeksforgeeks.org/a-data-structure-question/
Мин-Макс куча Я бы сказал, это ответ, как указано «user2357112», если наиболее частыми операциями являются findMin и findMax. BST может быть излишним, если мы на самом деле не хотим полностью упорядоченную структуру данных, вышеприведенное — это частично упорядоченная структура данных. Ссылка размещена выше.