Существует ли реализация "кучи" MinMax C++?
Я ищу алгоритмы как в stl (push_heap, pop_heap, make_heap) кроме со способностью вытолкать и минимальное и максимальное значение эффективно. Иначе удвойте законченную приоритетную очередь. Как описано здесь.
Любая чистая реализация двойной законченной приоритетной очереди также представляла бы интерес как альтернатива, однако этот вопрос главным образом о реализации "кучи" MinMax.
Мой google-fu не был плодотворен, но конечно, это должно существовать?
5 ответов
Если вы ищете реализацию алгоритма, попробуйте напрямую Google Code Search .
Есть ли причина, по которой вы не можете использовать std::set? Похоже, что это, вместе с некоторыми обертками для доступа и удаления set::begin() и --set::end() решит проблему. Я полагаю, что будет трудно найти что-то, что в целом может выполнять MinMax Heap намного быстрее, чем реализация set по умолчанию.
Я не могу найти хороших реализаций, но, поскольку никто другой тоже не может, я предполагаю, что вы напишете свою собственную, и в этом случае у меня есть для вас несколько полезных ссылок.
Документ, о котором, кажется, никто не упомянул, является первоначальным предложением для Min-Max-Heaps:
http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps. pdf
Я дважды реализовал кучу min-max из этой статьи (не на языке C) и нашел ее довольно тривиальной.
Улучшение, которое я никогда не реализовывал, - это Min-Max-Fine-Heap. Я не могу найти никаких хороших статей или ссылок в простой старой прекрасной куче, но я нашел одну в min-max-fine-heap, которая, по-видимому, работает лучше:
Не уверен, что это именно то, что вы ищете, но вот MinMax Heap, который я создал еще в университете. Это была часть более крупного проекта, поэтому здесь есть посторонняя ссылка на класс 'Stopwatch', который измерял производительность. Я не включаю этот класс, так как это не моя работа. Его несложно удалить, поэтому я оставляю ссылку на него как есть.
Код на snipplr
Чтобы использовать, просто создайте новый экземпляр кучи с любым типом, который вы хотите использовать. (Примечание, для пользовательских типов потребуется перегрузить операторы сравнения). Создайте массив этого типа, затем передайте его конструктору и укажите текущий размер массива и максимальный. Эта реализация работает только на переданном массиве, поскольку это единственное, что мне было нужно, но у вас есть все необходимое для реализации методов push и pop.