Удаление элементов из кучи

Question

Удаление элементов из кучи

Я сделал кучу. Мне любопытно, если что-то не так с моей функцией удаления:

int Heap::remove() {
if (n == 0)
exit(1);

int temp = arr[0];
arr[0] = arr[--n];
heapDown(0);
arr[n] = 0;

return temp;
}

void Heap::heapDown(int i)
{
int l = left(i);
int r = right(i);
// comparing parent to left/right child
// each has an inner if to handle if the first swap causes a second swap
//  ie    1   ->   3   ->   5
//      3   5    1   5    1   3

if (l < n && arr[i] < arr[l])
{
swap(arr[i], arr[l]);
heapDown(l);

if (r < n && arr[i] < arr[r])
{
swap(arr[i], arr[r]);
heapDown(r);
}
}
else if (r < n && arr[i] < arr[r])
{
swap(arr[i], arr[r]);
heapDown(r);

if (l < n && arr[i] < arr[l])
{
swap(arr[i], arr[l]);
heapDown(l);
}
}
}

Вот мой вывод

i1i2i3i4i5i6i7
p
Active heap: 7 4 6 1 3 2 5

r
Removed 7
r
Removed 6
p
Active heap: 5 3 4 1 2

Вот пример вывода моего учителя:

p
Active heap : 7 4 6 1 3 2 5
r
Removed 7
r
Removed 6
p
Active heap : 5 4 2 1 3
s
Heapsorted : 1 2 3 4 5

Хотя наши результаты совершенно разные, я, кажется, придерживаюсь принципа maxheap, чтобы все было ориентировано слева и для всех узлов parent> child (во всех случаях, которые я пробовал). Я пытаюсь сделать такие algs с нуля, так что, возможно, я просто делаю что-то действительно странное и неправильное (я бы посчитал это «неправильным», только если это> O (lg n), поскольку удаления предназначены для кучи). Есть ли что-то особенно «неправильное» в моем удалении? Спасибо,

http://ideone.com/PPh4eQ

3

algorithm c++data-structures heap heapsort

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Во-первых, я предполагаю, что вы имеете в виду, помимо того факта, что вам это не нужно, поскольку в стандартной библиотеке C ++ установлена вся функция управления кучей, включая make_heap, push_heap, pop_heap и даже sort_heap.

Тем не менее, я думаю, что я знаю, в чем ваша проблема. У вас есть ненужное движение элементов в вашей куче. Он имеет дело с алгоритмом обмена в куче: одна и та же проблема заметна как с левой, так и с правой стороны, поэтому я покажу первую:

if (l < n && arr[i] < arr[l])
{
swap(arr[i], arr[l]);
heapDown(l);

if (r < n && arr[i] < arr[r])
{
swap(arr[i], arr[r]);
heapDown(r);
}
}

Логика здесь не оптимальна для минимального движения. «Меньшее» состояние выталкиваемого элемента должно относиться к одной из двух основных категорий, и для каждой из них предпринимаются различные действия:

Элемент не менее чем или влево или вправо. Ничего не делать.
Элемент меньше чем или влево или вправо, поменять местами только с крупнейший, затем ехать в только это поддерево.

№ 2 выше в этом списке — проблема в вашем коде. ты поменяешься с меньшим, затем чем больше, если предмет < оставил < право. Я надеюсь, что это понятно. Если вы хотите, чтобы предложение исправило вашу логику, я могу предоставить его, но я думаю, что вы, возможно, справитесь с ним, если поймете, что я описал выше.

Спойлер

void Heap::heapDown(int i)
{
int l = left(i);
int r = right(i);
int x = 0;

if (l < n && arr[i] < arr[l])
{
x = l;
if (r < n && arr[l] < arr[r])
x = r;
}

else if (r < n && arr[i] < arr[r])
x = r;

if (x != 0)
{
swap(arr[i], arr[x]);
heapDown(x);
}
}

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

3