Я ищу алгоритмы, подобные тем, что были в stl (push_heap, pop_heap, make_heap), за исключением возможности эффективно использовать минимальное и максимальное значение. AKA с двойной остановкой приоритета. Как описано здесь.
Любая чистая реализация очереди с двойным завершением приоритета также представляла бы интерес в качестве альтернативы, однако этот вопрос в основном касается реализации MinMax Heap.
Мой google-fu не был плодотворным, но, безусловно, он должен существовать?
Если вы ищете реализацию алгоритма, попробуйте прямо Поиск кода Google.
Есть ли причина, по которой вы не можете использовать 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. Я не могу найти никаких хороших документов или ссылок на простой старой куче, но я нашел один на мини-мак-кучке, который, по-видимому, работает лучше:
Мой google-fu привел меня к следующему:
Не уверен, что это именно то, что вы ищете, но вот MinMax Heap, созданный еще в мои университетские дни. Это было частью более крупного проекта, поэтому есть посторонняя ссылка на класс "Секундомер", который измерял производительность. Я не включаю этот класс, поскольку это не моя работа. Это не сложно снять, поэтому я оставляю ссылку на него как есть.
Код snipplr
Чтобы использовать, просто создайте новый экземпляр кучи с любым типом, который вы хотите использовать. (Примечание. Пользовательские типы должны будут перегружать операторы сравнения). Создайте массив этого типа, а затем передайте его конструктору и укажите текущий размер массива и максимальный размер. Эта реализация работает поверх переданного массива только потому, что это единственное, что мне нужно, но у вас есть все необходимое для реализации push и pop-методов.
Извините за длинный код, но он отлично работает, но может затруднить чтение и может содержать некоторые ненужные переменные, и я не загружаю функцию Insert. Используйте его как include.h файл.
#include <math.h>
#define bool int
#define true 1
#define false 0
#define Left(i) (2 * (i))
#define Right(i) (2 * (i) + 1)
#define Parent(i) ((i) / 2)
void TrickleDown(int* A, int n)
{
int i;
for (i = 1; i <= n / 2; i++)
{
if (isMinLevel(i, n) == true)
TrickleDownMin(A, i, n);
else
TrickleDownMax(A, i, n);
Print(A, n);
printf("i = %d\n", i);
}
}
int isMinLevel(int i, int n)//i is on min level or not
{
int h = 2;
if (i == 1)
return true;
while (true)
{
if (i >= pow(2, h) && i <= pow(2, h + 1) - 1)
return true;
else if (i > n || i < pow(2, h))
return false;
h += 2;
}
}
void swap(int* a, int* b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
void TrickleDownMin(int* A, int i, int n)
{
int m, lc, rc, mc, lclc, lcrc, mlc, rclc, rcrc, mrc;
int child;
lc = Left(i);
if (lc > n) // A[i] has no children
return;
else
{
rc = Right(i);
mc = rc > n ? lc : (A[lc] > A[rc]) ? rc : lc;
child = true; // keep tracking m comes from children or grandchildren
// m = smallest of children and grand children
lclc = Left(lc);
if (lclc <= n)
{
lcrc = Right(lc);
mlc = lcrc > n ? lclc :(A[lclc] > A[lcrc]) ? lcrc : lclc;
mc = mlc > mc ? mc : mlc;
if (mc == mlc)
child = false;
}
rclc = Left(rc);
if (rclc <= n)
{
rcrc = Right(rc);
mrc = rcrc > n ? rclc : (A[rclc] > A[rcrc]) ? rcrc : rclc;
mc = mrc > mc ? mc : mrc;
if (mc == mrc)
child = false;
}
m = mc;
if (!child)//m is one of the child of i
{
if (A[m] < A[i])
{
swap(&A[m], &A[i]);
if (A[m] > A[Parent(m)])
swap(&A[m], &A[Parent(m)]);
TrickleDownMin(A, i, m);
}
}
else //m is child of i
{
if (A[m] < A[i])
swap(&A[i], &A[m]);
}
}
}
void TrickleDownMax(int* A, int i, int n)
{
int m, lc, rc, mc, lclc, lcrc, mlc, rclc, rcrc, mrc;
int child;
lc = Left(i);
if (lc > n)//A[i] has no children
return;
else
{
rc = Right(i);
mc = rc > n ? lc : (A[lc] < A[rc]) ? rc : lc;
child = true; //keep tracking m comes from choldren or grandchildren
//m = greatest of children and grand children
lclc = Left(lc);
if (lclc <= n)
{
lcrc = Right(lc);
mlc = lcrc < n ? lclc : (A[lclc] < A[lcrc]) ? lcrc : lclc;
mc = mlc < mc ? mc : mlc;
if (mc == mlc)
child = false;
}
rclc = Left(rc);
if (rclc <= n)
{
rcrc = Right(rc);
mrc = rcrc < n ? rclc : (A[rclc] < A[rcrc]) ? rcrc : rclc;
mc = mrc < mc ? mc : mrc;
if (mc == mrc)
child = false;
}
m = mc;
if (!child)//m is one of the child of i
{
if (A[m] > A[i])
{
swap(&A[m], &A[i]);
if (A[m] < A[Parent(m)])
swap(&A[m], &A[Parent(m)]);
TrickleDownMax(A, i, m);
}
}
else //m is child of i
{
if (A[m] > A[i])
swap(&A[i], &A[m]);
}
}
}
void Print(int* a, int n)
{
int i;
for (i = 1; i < n + 1; i++)
{
printf("%d ", a[i]);
}
}
int DeleteMin(int* A, int n)
{
int min_index = 1;
int min = A[1];
swap(&A[min_index], &A[n]);
n--;
TrickleDown(A, n);
return min;
}
int DeleteMax(int* A, int n)
{
int max_index, max;
max_index = n < 3 ? 2 : (A[2] > A[3]) ? 2 : 3;
max = A[max_index];
swap(&A[max_index], &A[n]);
n--;
TrickleDown(A, n);
return max;
}