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

Самый простой способ — просто использовать бинарное дерево поиска, как рекомендует М. Шоу.

Если вам нужно построить это поверх двоичных куч, то в каждой куче, рядом с каждым элементом, сохраните позицию элемента в другой куче. Каждый раз, когда вы перемещаете элемент в одной куче, вы можете сразу перейти к его положению в другой куче и обновить его. Когда вы выполняете delete-min или delete-max, дорогостоящее линейное сканирование в другой куче не требуется.

Например, если вы храните std::pairs с first в качестве значения элемента и second в качестве позиции в другой куче, замена двух элементов в минимальной куче при обновлении их аналогов в максимальной куче может выглядеть следующим образом:

swap(minheap[i], minheap[j]);
maxheap[minheap[i].second].second = i;
maxheap[minheap[j].second].second = j;

Вы можете создать хеш-таблицу для элементов кучи, которая используется двумя кучами. Таблица индексируется по значению элемента кучи. Значение хешированного сегмента может быть структурой, состоящей из индекса массива в minHeap и maxHeap соответственно.

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

E.g.,

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] — это расположение в минимальной (или максимальной) куче индекса 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/