Где ошибка, как из рекурсии цикл сделать?

Question

[SergeySerge11]

Метод для очереди с приоритетом?

// не правильно работает
       private void siftDown2(int i)
       {
           int l ;
           int r ;
           int j = i;
           do
           {
               l = getLeft(i);
               r = getRight(i);
               j = i;
               if (l < size && elems[j] < elems[l])
                   j = l;
               if (r < size && elems[j] < elems[r])
                   j = r;
               if (j != i)
               {
                   swap(i, j);
                   i = j; 
               }

           } while (j != i);
       }
// работает
       private void siftDown(int i)
       {
           var l = getLeft(i);
           var r = getRight(i);
           int j = i;
           l = getLeft(j);
           r = getRight(j);
           j = i;
           if (l < size && elems[j] < elems[l])
               j = l;
           if (r < size && elems[j] < elems[r])
               j = r;
           if (j != i)
           {
               swap(i, j);
               siftDown(j);
           }
       }

Другой вопрос, много раз ее реализовывал, есть ли в c# или где-то реализация очереди с приоритетом с произвольным доступом, уже кучу раз реализовал, лень постоянно.

Comments

[Василий Банников]

есть ли в c# или где-то реализация очереди с приоритетом с произвольным доступом, уже кучу раз реализовал, лень постоянно.

PriorityQueue?
И зачем много раз реализовывать, если можно реализовать 1 раз?

[#]

SergeySerge11,

{
                   swap(i, j);
                   i = j; 
               }

что за swap вы используете?
разве по итогу не сразу i = j; ???

[#]

SergeySerge11 как вариант своп на основе кортежей(a, b) = (b, a);

[#]

Василий Банников, .. кажется за право "токсичности" скоро можно будет и спорить ;)))
только шутка! ))

[MVV]

#, swap там по смыслу алгоритма - обмен i-го и j-го элементов массива, а не i и j.
Это, вообще-то - алгоритм построения heap (по-русски мне нравится вариант перевод из советского перевода 3-го тома Кнута - "пирамида"), у Кнута он появляется как часть(полвинка, реально) heap sort. Можете заглянуть туда за подробностями, пирамида там, правда, строится в обратном порядке, чем у автора вопроса - в начало вытаскивается больший элемент, а не меньший. Ну - или в любую книжку по алгоритмам, где heap sort есть.
PS Кстати, если элементы массива не слишком длинные (помещаются в операнд команды XOR), то предки завещали нам менять их в памяти прямо по месту, тремя команами XOR - есть такой трюк. Но это уже, наверное, не для C#.

[#]

MVV, было желание копнуть алгоритм, да поленился ))
давайте вспомним что и автор, и вы в примере, использовали упрощение ))
но и предлагаемая схема на кортежах его так же допускает ;))

Кстати, если элементы массива не слишком длинные (помещаются в операнд команды XOR), то предки завещали нам менять их в памяти прямо по месту, тремя команами XOR - есть такой трюк. Но это уже, наверное, не для C#.

ну не факт.. новые поколения дотнет вернулись к железу лицом.. на грани ассемблерных вставок )).. но естественно тут дело будет в типах данных )))

[Василий Банников]

#,

ну не факт.. новые поколения дотнет вернулись к железу лицом.. на грани ассемблерных вставок )).. но естественно тут дело будет в типах данных )))

А ещё JIT работает)

.. кажется за право "токсичности" скоро можно будет и спорить ;)))

Да я давно уж не токсичу.

[#]

Василий Банников, https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D0%B9%D...
)))
в свое время добавил возможность ассемблерных вставок в TP ... ох я тогда покуражился во славу СССР ... сори за офтоп )))

[MVV]

#, не страшно. Я этот алгоритм быстро распознал не потому, что я все алгоритмы наизусть выучил, а потому что я в ту область недавно лазил чисто по собственным делам и собственному любопытству - вон он у меня в голове и закэшировался.
PS Ну а про фокус с тремя XOR в .NET пусть JIT беспокоится - он наверняка о нем знает: больно уж древний он.

[#]

MVV, все сравнимо )) Кнута мне давали еще в 88 году )) не скажу что все 4 тома осилил, но заглядывал ))
.. упс.. их уже 7... но тогда видел 4 ))
по исходному вопросу - было захотелось перепроверить.. ан нет.. лень, да и жизнь свое требует ))
успехов в кодинге! )))

[SergeySerge11]

Там ошибка была в swap методе, и уже 2 раз за 2 года ее повторил, забыл помимо замены элементов, еще индексы обновить, для поддержки произвольного доступа по индексу.(хотя ее не забыл, но не так менял)

Answer 1

[MVV]

//...declarations and initializations omitted
           do
           {
               //...some code omitted
               if (j != i)
               {
                   swap(i, j);
                   i = j; 
               }
           } while (j != i);

Не работает, потому что вы сначала присваете j значение i, если они не равны, а потом, в условии продолжения цикла, сравниваете их значения. Естественно, они будут равны и выход их цикла получится на первой же итерации. Проверять i==j как условие выхода из цикла надо чуть раньше, например, так:

//...declarations and initializations omitted
           do
           {
               //...some code omitted
               if (j != i)
               {
                   swap(i, j);
                   i = j; 
               }
               else break;
           } while (true);

Ну, а что до второго вопроса, то в .NET, начиная с 6.0 есть класс System.Collections.Generic.PriorityQueue<TElement,...

Comments

[#]

.. уж простите, просто зудит, сам бы сделал так примерно

//...declarations and initializations omitted
           for(var stop=false; !stop; )
           {
               //...some code omitted
               if (!(stop = (j == i))
               {
                   swap(i, j);
                   i = j; 
               }
           }

но стоит тестить.. просто не люблю многострочность ))
//...some code omitted тоже можно вынести в лямбду, тогда код станет и прозрачнее, и тестируемее
.. и проверку тем более в лямбду ;))
.. тогда цикл выродился бы в одну строку ;))

[#]

SergeySerge11,

.. или вообще так

//...declarations and initializations omitted
           for(var stop=false; !stop; )
           {
               //...some code omitted
               if (!(stop = (j == i))
                   (i, j) = (j, i);
           }

[#]

SergeySerge11, повторюсь, что //...some code omitted тоже легко вынести в лямбду, тогда тело цикла вырождается в одну строку. и код читаемый, поддерживаемый, тестируемый

[MVV]

//...declarations and initializations omitted
for(stop=false; !stop; )
{
//...some code omitted
if (!(stop = (j == i))
(i, j) = (j, i);
}

#, не годится: swap там должен менять значения элементов массива с указанными индексами. См. мой комментарий к самому вопросу.

[#]

MVV, см исходный код буквально )))... да и собственный ответ.. пока не вижу повода для спора ))

[#]

MVV,
- swap не указан как метод меняющий элементы массива/перечисления (или это не показано..
- swap может быть определен как метод меняющий и переменные индексов, в тч опционально ))
... кхм... не люблю многострочность.. считаю ее главным источником недопониманий и ошибок ))