Порядок обновления кучи
вот рабочий код для алгоритма heapsort, мой вопрос заключается в том, что при создании кучи я меняю условие в коде на
for ( int i = 0 ; i < dim/2-1; i ++)
что я думаю, что это цикл for, но в обратном порядке, и я думаю, что процесс обновления кучи совершенно такой же (в моей голове мы проходим обновление состояния кучи для каждого индекса от 0 до конца массива), почему алгоритм больше не работает? Неправильно написано другое условие или просто алгоритм рассчитан на работу с уменьшением индекса i? Спасибо
#include <stdio.h>
void Scambia( int *px, int *py);
void Aggiornaheap( int *pa, int i, int j);
int main(void)
{
int a[256];
int n;
int dim = 0;
// Lettura dell’input da tastiera
while (scanf("%d\n", &n) == 1)
{
a[dim] = n;
dim++;
}
// heap creation
for ( int i = dim/2-1 ; i >= 0; i --)
{
Aggiornaheap(a, i, dim);
}
//Heapsort
for ( int i = dim-1; i >= 0; i --)
{
Scambia(&a[0], &a[i]);
Aggiornaheap(a, 0, i-1);
}
for ( int i = 0; i < dim; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
void Scambia( int *px, int *py)
{
int temp;
temp = *px;
*px = *py;
*py = temp;
}
void Aggiornaheap( int *pa, int i, int j)
{
int k;
if ( 2*i == j )
{
if ( pa[i] < pa[j])
Scambia(&pa[i], &pa[j]);
}
if ( 2*i < j )
{
if ( pa[2*i] > pa[2*i+1] )
k = 2*i;
else k = 2*i+1;
if ( pa[i] < pa[k])
{
Scambia(&pa[i], &pa[k]);
Aggiornaheap(pa, k, j);
}
}
}
Ответы 1
Необходимо, чтобы узлы посещались в обратном порядке. Алгоритм не будет правильно выполнять свою работу, если вы измените этот порядок.
Возьмем, к примеру, это входное дерево, которое нужно сгруппировать в мини-кучу: [2,4,3,1], которое можно визуализировать следующим образом:
2
/ \
4 3
/
1
Затем обратите внимание, что значение 1 не сможет подняться вверх, когда вы измените цикл for, чтобы двигаться вперед. Давайте просто попробуем это. Когда i==0 ничего не меняется местами, потому что 2 меньше, чем его дети. Когда i==1, то 4 будут заменены на 1, и тогда цикл завершится. Ясно, что это не создало допустимую кучу.
Однако, если мы начнем с i==1, что вызывает обмен 1 на 4, и только потом имеет i==0, то мы снова поменяем местами 1, чтобы двигаться вверх:
1
/ \
2 3
/
4
Один комментарий о вашем коде. Похоже, вы работаете с массивами с нулевым индексом, с корневым элементом в 0, но в этом случае дочерние элементы находятся в i*2+1 и i*2+2, не меньше, как мы видим в вашем коде.
Поскольку сейчас используется формула индекса, в некоторых ситуациях она не работает. Это просто неправильно, и поэтому это большая проблема. Да, исправьте формулу. Альтернативой является запуск с 1, но он просто тратит впустую запись с индексом 0, поэтому я бы исправил формулу. См. также Википедия, который предполагает, что индекс начинается с 1. Но я бы сделал это только в том случае, если язык программирования организует такие массивы (начиная с индекса 1). Для индексации с отсчетом от нуля я бы изменил формулу.
Последний вопрос: если начать с нуля и не изменить формулу, получится дерево, имеющее только одного корневого сына, а затем являющееся бинарным деревом для всех остальных узлов, я прав? Разве это еще не куча? Спасибо
Да это правда. Но определение двоичной кучи состоит в том, что это двоичное дерево полный.
Так что с точки зрения определения это явно другой объект, и поэтому он не может быть двоичной кучей. С точки зрения алгоритмической работы, я думаю, все еще работает нормально, потому что корень в двоичном дереве, представляющем двоичную кучу, является максимальным элементом, поэтому «нулевой» элемент будет сравниваться с корнем, переключаться в случае, если он меньше, а затем как цепная реакция при необходимости будет изменять все дерево ниже. Явно ничего формального... Что вы об этом думаете?
Но бинарные кучи были изобретены для повышения производительности. Теперь у вас будет в среднем дерево, которое имеет на один уровень больше, чем двоичная куча. Так что с точки зрения производительности вы должны просто придерживаться структуры данных, как это было задумано.
О да, с точки зрения производительности это понижение, я не думал об этом. Я изменю формулу, но я хочу сказать, что (если я понял, как работает куча и сортировка кучей) код выполняет свою работу, он просто работает хуже из-за этого ненужного верхнего уровня.
Во втором блоке if проверьте, что происходит, когда i равно 0: pa[2*i] > pa[2*i+1]. Если это условие истинно, то должен произойти обмен, но затем вы устанавливаете k равным корню, поэтому обмена не произойдет, и корень останется больше, чем его единственный дочерний элемент, что неверно.
Спасибо, я понимаю, почему это не работает с переключением условия for, теперь, с вашим наблюдением за индексом, я пытаюсь понять, большая ли это проблема, потому что я запустил пару примеров, и, похоже, все работает нормально , как вы думаете, стоит изменить индекс или сделать так, чтобы массив начинался с 1?