1:30 Формулы: для i элемента его левый потомок вычисляется как i*2+1, а его правый потомок вычисляется как i*2+2 (при условии, что индексирование начинается с 0)
Вы детально рассказываете реализацию идеи, но саму идею ПРОСТЫМИ СЛОВАМИ не рассказали. А по сути, мы хотим, получить как-то бинарное дерево, отсортированное по величине значений элементов. Проще начать сортировку с нижних троек, постепенно сортируя дерево вверх. Почему иногда происходит спуск вниз, если мы изначально поднимаемся от ветвей к корню? Потому что у нас цель получить отсортированное по убыванию значений дерево, а при перестановке значений у любого узла, одна из его ветвей может оказаться неотсортированной, что противоречит главной задаче - сортировке, и если не сделать спуск сразу, то алгоритм сортировки будет намного сложнее. Детали - это хорошо, но большинство академических преподавателей страдает невозможностью простыми словами изложить простую идею, которая изначально и приходит создателям в голову, когда они лежат в постели, сидят на унитазе, или едят. А так нам приходится пробираться из дебрей реализации к простой изначальной идее. А так, лайк за видео!
потому что поиск максимума у тебя всегда будет занимать о(n) и для n операций выйдет о(n^2). Благодаря структуре кучи мы каждый раз получаем самый максимум в первом элементе массива (нулевом если быть точным), далее свопаем его с последним элементом, далее просеиваем этот новый первый элемент массива уже за logn т.к. на каждом уровне просеивания мы двигаемся логарифмически . В итоге получается n операций по logn. Пирамидальная сортировка хуже по скорости (на константу) чем те же быстрая и слиянием, но гораздо лучше вплане потребления памяти: в каждый момент времени в буфере находится максимум один элемент (потребление по памяти выходит о(1)). Это преимущество пирамидальной сортировки и является решающим в задачах где очень важно сортировать элементы в условиях ограничения расходуемой памяти.
@@АлыИсмаилов-г1о уф.. спасибо большое за разъяснение. Но для общего понимания для меня слияние все равно гораздо проще для понимания и реализации, чем эта) видимо надо написать или применить ее пару тройку раз тогда может уложится получше)
@@АлыИсмаилов-г1о как раз тематика видео и должна была наглядно показать то что вы говорите. Но она этого не делает. По видео создаётся впечатление что сравнение происходит со ВСЕМИ элементами, что бы там не писали про сложнгости олгоритма заменяя понятные простому обывателю фразы проде "по одному сравнению на каждый элемент" буквами "On" и другими вы ясность не вносите. фактически достаточно было бы сказать что благодоря тому что пирамида "предсортирована" предыдрущей итерацией - это позволяет выполнить меньше сравнений чем при полном переборе.
Не очень хорошее объяснение, никакие элементы на последнем этапе не "выкидываются" из дерева, а лишь переставляются с рекурсивной проверкой. Это некоторая "авторская модификация" алгоритма
Ну вы хоть бы отредактировали своё выступление! Что значит "только спускаемся на уровень выше ..... спускаемся на уровень выше" ? И не надо оправдываться, что тут всё понятно, и что вы имели в виду вот именно этот или тот конкретный уровень ..... :)))
Скорее просто вводим формулу, определяющую по индексам, кто кому потомок, кто кому родитель. Таким образом мы создаем связь между элементами массива по принципу бинарного дерева. Это, например, значит, что элемент под номером 5 (согласно нумерации под массивом на видео) знает, что может работать только с элементами 10, 11 в статусе родителя и с элементом 2 в качестве потомка. Теперь, имея начальный массив и зная как связаны между собой его элементы, начинаем применять алгоритм, который позволяет за оптимальное количество перестановок значений подобрать порядок, соответствующий ожидаемой сортировке.
Очень хорошая визуализация и понятное объяснение. Визуализация прям помогла понять, как этот алгоритм работает.
Фраза "спускаемся на уровень выше" на 6:14 взорвала мой мозг.
Благодарю, это самое понятное визуальное представление алгоритма пирамидальной сортировки.
Дай Бог тебе здоровья, чётко объяснил и разложил суть сортировки
Спасибо! Лучшее наглядное объяснение.
Прекрасное объяснение! Спасибо огромное за урок!!!
Спасибо, очень наглядно. Благодаря вам понял алгоритм
1:30 Формулы: для i элемента его левый потомок вычисляется как i*2+1, а его правый потомок вычисляется как i*2+2 (при условии, что индексирование начинается с 0)
Большое спасибо, всё очень понятно объяснено!
Далеко не лучшее объяснение, но отличная визуализация сильно выручает
Качество видео просто шик. Я и сам занимаюсь гайдами, но от вашего прикурил!
Отлично подготовленная презентация! Спасибо!
Обалденно, спасибо огромное, продолжай выпускать свои ролики, пожалуйста!
Спасибо огромное! Очень хорошо и наглядно объясняете
крутое наглядное объяснение!спасибо за видео!
Мужик, ты реально хорош, спасибо тебе!
Вы детально рассказываете реализацию идеи, но саму идею ПРОСТЫМИ СЛОВАМИ не рассказали. А по сути, мы хотим, получить как-то бинарное дерево, отсортированное по величине значений элементов. Проще начать сортировку с нижних троек, постепенно сортируя дерево вверх. Почему иногда происходит спуск вниз, если мы изначально поднимаемся от ветвей к корню? Потому что у нас цель получить отсортированное по убыванию значений дерево, а при перестановке значений у любого узла, одна из его ветвей может оказаться неотсортированной, что противоречит главной задаче - сортировке, и если не сделать спуск сразу, то алгоритм сортировки будет намного сложнее.
Детали - это хорошо, но большинство академических преподавателей страдает невозможностью простыми словами изложить простую идею, которая изначально и приходит создателям в голову, когда они лежат в постели, сидят на унитазе, или едят. А так нам приходится пробираться из дебрей реализации к простой изначальной идее.
А так, лайк за видео!
Золотые слова. Уже статьи 4 прочел, не разобрался. Решил видеоролики посмотреть.
Лучше и наглядное объяснение. Уже день пытаюсь вдуплить, почему да как.
Спасибо! Разъяснено понятно!
Отличное объяснение, спасибо!
Визуально понятно, но не понимаю, как это реализовать в виде кода
Такая же хуйня, заебало программирование в универе
@@andrey-ei4px оо, да понимаю. Нафиг вообще это прога нужна не на программиста поступал
Спасибо вам
Здравствуйте! Можете, пожалуйста, в ближайшем будущем разобрать Quick-Sort и Merge-Sort? А так, спасибо Вам за видео!! Все очень круто и понятно :)
Благодарен за видео!
Отличная подача!
огонь!!!
Графика хорошо показывает алгоритм
Спасибо огромное
блеск! спасибо))
Thanks.
спасибо за видео
ты что Бог?
spasibo vam bolshoe
Спасибо!
Если в дереве всё равно сравниваются все элементы как минимум 1 раз - почему бы не заменить все эти перестановки на просто поиск максимального числа?
вот аналогично сижу и не понимаю этого... куча сравнений, постоянных перестановок туда сюда
потому что поиск максимума у тебя всегда будет занимать о(n) и для n операций выйдет о(n^2). Благодаря структуре кучи мы каждый раз получаем самый максимум в первом элементе массива (нулевом если быть точным), далее свопаем его с последним элементом, далее просеиваем этот новый первый элемент массива уже за logn т.к. на каждом уровне просеивания мы двигаемся логарифмически . В итоге получается n операций по logn. Пирамидальная сортировка хуже по скорости (на константу) чем те же быстрая и слиянием, но гораздо лучше вплане потребления памяти: в каждый момент времени в буфере находится максимум один элемент (потребление по памяти выходит о(1)). Это преимущество пирамидальной сортировки и является решающим в задачах где очень важно сортировать элементы в условиях ограничения расходуемой памяти.
@@АлыИсмаилов-г1о уф.. спасибо большое за разъяснение. Но для общего понимания для меня слияние все равно гораздо проще для понимания и реализации, чем эта) видимо надо написать или применить ее пару тройку раз тогда может уложится получше)
@@АлыИсмаилов-г1о как раз тематика видео и должна была наглядно показать то что вы говорите. Но она этого не делает. По видео создаётся впечатление что сравнение происходит со ВСЕМИ элементами, что бы там не писали про сложнгости олгоритма заменяя понятные простому обывателю фразы проде "по одному сравнению на каждый элемент" буквами "On" и другими вы ясность не вносите. фактически достаточно было бы сказать что благодоря тому что пирамида "предсортирована" предыдрущей итерацией - это позволяет выполнить меньше сравнений чем при полном переборе.
святой
спасибо
Без примеров кода, польза от этого видео - минимальна.
просто признайся что хотел скопипастить
@@IvanFedulov, нет.
Фронтендер знать такое не должен - никогда в работе не пригодится. Данное знание опционально.
Но все равно интересно для себя
@@ExileHB , написал коммент только потому, что вначале автор видео сказал: "... алгоритм, который должен знать каждый программист..."
Дак он сказал каждый программист, а фронтендер не программист))
Это зависит от воронки кандидатов. Если их много то обычно делают тесты на алгоритмы вне зависимости от направления : )
@@zhimbura, а кто же тогда фронтендер?
"order by" - решает фсе!
Не очень хорошее объяснение, никакие элементы на последнем этапе не "выкидываются" из дерева, а лишь переставляются с рекурсивной проверкой. Это некоторая "авторская модификация" алгоритма
мы просто длину рассматриваемого массива уменьшаем на 1 пока она не станет равно 0))) все ок он поясняет
Ну вы хоть бы отредактировали своё выступление! Что значит "только спускаемся на уровень выше ..... спускаемся на уровень выше" ? И не надо оправдываться, что тут всё понятно, и что вы имели в виду вот именно этот или тот конкретный уровень ..... :)))
Вообще НИЧЕРТА не понял. Т.е. мы сначала строим бинарное дерево, а потом из него восстанавливаем массив в отсортированном виде?
Скорее просто вводим формулу, определяющую по индексам, кто кому потомок, кто кому родитель. Таким образом мы создаем связь между элементами массива по принципу бинарного дерева. Это, например, значит, что элемент под номером 5 (согласно нумерации под массивом на видео) знает, что может работать только с элементами 10, 11 в статусе родителя и с элементом 2 в качестве потомка.
Теперь, имея начальный массив и зная как связаны между собой его элементы, начинаем применять алгоритм, который позволяет за оптимальное количество перестановок значений подобрать порядок, соответствующий ожидаемой сортировке.
Да, но при этом бинарное дерево и хранится в самом массиве, а два потомка родителя или родитель потомка легко вычисляются по простой формуле.