>>42967
И да, проблема в том, что сейчас этот код зависает, и я не вижу, в каком месте может возникать зацикливание.

>>42968
Отладочный вывод запили в функции и увидишь на каком этапе начинается зацикливание. В 2015 году программисты даже этого не знают, пушка просто.

>>42969
Хули вы хотели, блядь. Отладочный вывод не наука! Нет теоремы, доказывающей, что он помогает! А пэтему мы будем учить студентов его использовать!!! Это для php/C#-быдлеца же. На хую вертел эти универы.

>>42969

> Отладочный вывод запили в функции и увидишь на каком этапе начинается зацикливание

Я навскидку могу сказать, что скорее всего зацикливание в функции min_child, но даже если я найду точное место, где происходит зацикливание, я все равно не буду знать, как правильно переделать функции для работы с d-арной кучей.
>>42970
Неосилятор математики подгорел. Тебя после 35 лет спишут как биомусор и возьмут вместо тебя молодого, потому что ценность программиста с годами падает. Лучше бы ты глубоко изучал алгебру, сейчас бы обмазывался где-нибудь в Германии когомологиями за бабосы. Правильно выбирай профессию.

Главная проблема программероплебеев в том, что они так и не смогли постигнуть красоту математики. Программер никогда не испытал то удовольствие, когда при решении задачи на доказательство ты чувствуешь и видишь внутренним взором, как у тебя в голове строятся ассоциативные связи между теоремами и определениями. Соответственно, дойти до того уровня развития, когда математикой можно зарабатывать деньги, им уже невозможно. Драгоценное время программистишки потратили на пердолинг с отладчиком. Такая приземленность свойственна аутистам. С одной стороны они кажутся интеллектуалами, потому что помнят много технических деталей, но с другой - аутист ни в чем не разбирается глубоко, у него нет потребности изучать фундаментальные части чего бы то ни было. Отсутствует то тонкое мышление, которое связывает между собой разные понятия и теоремы и дает профит. Зато аутисты хорошо могут в рутинные занятия.

>>42971

> Я навскидку могу сказать, что скорее всего

Не гадай @ Измеряй.

> все равно не буду знать, как правильно переделать функции

Это не поможет? http://www.intuit.ru/studies/courses/100/100/lecture/2927

>>42973

> Это не поможет?

Да как раз по псевдокоду из этой статьи я и писал свои функции. Поэтому удивительно, что они приводят к зависанию.

>>42971

> Неосилятор математики подгорел. Тебя после 35 лет спишут как биомусор и возьмут вместо тебя молодого, потому что ценность программиста с годами падает. Лучше бы ты глубоко изучал алгебру, сейчас бы обмазывался где-нибудь в Германии когомологиями за бабосы. Правильно выбирай профессию.

Замечательно но программирование само по себе тоже нужно учить как-то, речь же об отсутствии программировании шла, а не о математике. Да и ничего там не падает, если обновлять знания. Скажешь, на рынке есть старики без работы, что ли? Мы бы тогда уже давно бы все вакансии позакрывали бы.

>>42972
Да и чего его там пердолить этот отладчик, надо нащупать три кнопки где-то сверху или снизу хуё моё. На это уйдёт минут 20-30. Можешь загуглить, если совсем как пробка.

>>42975

> Скажешь, на рынке есть старики без работы, что ли?

Да, у нас такой преподает, он и про отладочный вывод говорил, и давал программировать такие задачи, которые при неправильном ООП-проектировании доставляют баттхерт и приводят к обрастанию костылями, показывал нам, как все этого избежать. Думаешь, он бы преподавал в универе, если бы был нужен?

>>42976
А что отладчик? Даже если я найду место зависания, это ничего не решит, потому что здесь не программная энтерпрайз логика "если-то", а алгоритм, и здесь надо детально знать алгоритм, чтобы понять, почему он зависает.

>>42977

> А что отладчик? Даже если я найду место зависания, это ничего не решит, потому что здесь не программная энтерпрайз логика "если-то", а алгоритм, и здесь надо детально знать алгоритм, чтобы понять, почему он зависает.

Как бы ты без этого вообще написал его тогда? Иди курить алгоритм тогда. Наугад пишешь, что ли?

> Думаешь, он бы преподавал в универе, если бы был нужен?

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

>>42978

> Как бы ты без этого вообще написал его тогда? Иди курить алгоритм тогда. Наугад пишешь, что ли?

Просто у меня уже все в голове смешалось от большого числа статей по этим d-арным пирамидам. Где-то в реализации есть функции parent(i) и child(i) с пересчетом, соответствующим арности пирамиды, где-то ералиазция такая, как у меня, и все вместе это непонятно, и примеров д-арных пирамид нету толковых. Что можно почитать о перестроении массива в n-арное дерево?

>>42977

> Даже если я найду место зависания

То ты станешь внимательнее смотреть туда. Ошибка может быть не только в неверной реализации алгоритма, а в банальной невнимательности - что-нибудь не туда вписал или ошибся на единицу в условии (самая частая ошибка при обработке массивов).

Зависание все-таки происходит в этом цикле. https://ideone.com/kTtV2H
Эта функция точно выглядит как в статье выше, что может быть не так?

Заметил, что у меня было вместо s = minchild(a, s, n); написано s = minchild(a, i, n); Но когда исправил, цикл все равно не останавливается.

>>42982
1) А зачем там вообще эти вызовы своп? Там же i = s должно быть достаточно. Или что? По ходу, это и есть ошибка.

> int s = i*d + 1;

2) Первый ребёнок - это же id. А дальше id+1, ... id + (d-1). Всего d детей. Первый ребёнок в переборе в минчайлде пропущен. (i + 1)d - это уже второй родитель по идее. Но, может, там конечно другая нумерация, но подозрительно

>>42983
3) И при просеиваниях должны же быть помены местами самих значений тоже, а не просто выбор места, куда преземлиться. Ну да, вот своп как раз и должен менять знеачения местами, а не индексы, теперь понятно.

>>42984
4) Да, и зачем цикл построения пробегает только первые (n - 1)/d значений? Он же должен просееять вниз весь массив. Там должно выходить же NlogN - N просеиваний вниз, по logN каждая.

>>42983

> 2) Первый ребёнок - это же id.

Первый ребёнок - это
child = parent * d + 1 исходя из формулы для родителя:
parent = (i - 1) div d А вообще индексы детей:
child1 = parent * d + 1 ... childN-1 = parent * d + (d - 1) ... childN = parent * d + d

>>42967
В общем ОП, вот тебе рабочий всплывающий и тонущий пример на ПАЙТОНЕ, а я покатился спать - завтра на работу.

>>42986
Корень на нуле или на единице?

>>42988
Корень - array[0].

>>42987
Да, у меня тут ошибка в minChild(), первое же условие должно быть

if ( nodeIndex * d + 1 ) >= len(array): Иначе может произойти вылет за границы.

>>42990
А, всё, да, тут всё правильно. Но в свопе ошибка точно. И по идее в границе цикла в билде тоже. Там должноы быть std::swap(a[i], a[s]); У тебя переменная i вообще не меняется вот и зацикленность.

>>42991
Это у ОПа ничего не меняется, а в моём питонопримере всё меняется! Только с условием накосячил, но поправил.

>>42987
Нашёл ещё одну ошибку у себя. Ну как ошибку - особенность поведения. На этих функциях алгоритм сортировки двоичной кучи не работает, потому что размер массива вычисляется там внутри. А требуется, чтобы он передавался снаружи, поскольку после окучивания массива надо обменивать корень с последним элементом и топить корень, на каждой итерации урезая размер обрабатываемого массива.