При объяснении построения бинарной кучи в узле под индексом #4 находится значение 31. Но его родительский элемент (#2) имеет значение 23, что нарушает последнее условие бинарной кучи.
Спасибо что заметили, там действительно heapify я не выполнил до конца.. нужно было применить heapify к обоим потомкам (#2) что бы и продвинуло его на правильную позицию.
касаемо in-place сортировок, более того скорость алгоритма может возрастать (время уменьшаться), засчёт процессорного кэша, суть в том что если идут частые обращения в память по одному адресу(in-place), то что бы не гонять данные по шине от РАМ до процессора - процессор их кэширует у себя, соответственно скорость возрастает
13:05, не правильно, 2-ой вариант добавления не подходит. Нельзя сдвинуть элементы вниз, которые остались на пути к пустому месту (так вы сказали). Представьте, если до "сдвига вниз", значения элементов 4 и 5 (т.е. 9 и 11) поменять местами, дальше ваша логика сломается, т.к. будет нарушена целостность кучи. Посмотрел два ролика с вашего канала. Объясняете доходчиво. Но в двух роликах вы "ошиблись" на банальных вещах. Первый ваш ролик "сортировка слиянием", вы сказали что дополнительная память НЕ выделяется для той сортировки. Может быть, так люди будут больше комментировать ;). Больше вам просмотров, и лайков! И вы снимайте ещё!!!
В чем ломается логика? когда на место элемента ставится еще больший все поддерево остается валидным, как сделать in-place написал вам в комментах ruclips.net/video/6woBwlm1tRM/видео.html В банальных вещах я может и ошибаюсь, но думаю не в этом случае =)
@@lambdaway Перечитал свой коммент, который был написан год назад и он мне показался надменным. Извините). Сейчас я уже не смогу вспомнить, что имел ввиду. Возможно я ошибся, а возможно нет. В тот момент, я читал книгу Кормена (она не совсем простая), и старался каждый алгоритм сортировки реализовывать и разбирать. Как будет время (не скоро), напишу ответ. Кстати, при разборе алгоритмов сортировки, я частенько обращался к вашим роликам. Спасибо!
всё предельно понятно спасибо))
нигде не мог найти и тут ваше видео)
При объяснении построения бинарной кучи в узле под индексом #4 находится значение 31. Но его родительский элемент (#2) имеет значение 23, что нарушает последнее условие бинарной кучи.
Спасибо что заметили, там действительно heapify я не выполнил до конца.. нужно было применить heapify к обоим потомкам (#2) что бы и продвинуло его на правильную позицию.
касаемо in-place сортировок, более того скорость алгоритма может возрастать (время уменьшаться), засчёт процессорного кэша, суть в том что если идут частые обращения в память по одному адресу(in-place), то что бы не гонять данные по шине от РАМ до процессора - процессор их кэширует у себя, соответственно скорость возрастает
13:05, не правильно, 2-ой вариант добавления не подходит. Нельзя сдвинуть элементы вниз, которые остались на пути к пустому месту (так вы сказали).
Представьте, если до "сдвига вниз", значения элементов 4 и 5 (т.е. 9 и 11) поменять местами, дальше ваша логика сломается, т.к. будет нарушена целостность кучи.
Посмотрел два ролика с вашего канала. Объясняете доходчиво. Но в двух роликах вы "ошиблись" на банальных вещах. Первый ваш ролик "сортировка слиянием", вы сказали что дополнительная память НЕ выделяется для той сортировки.
Может быть, так люди будут больше комментировать ;). Больше вам просмотров, и лайков! И вы снимайте ещё!!!
В чем ломается логика? когда на место элемента ставится еще больший все поддерево остается валидным, как сделать in-place написал вам в комментах ruclips.net/video/6woBwlm1tRM/видео.html В банальных вещах я может и ошибаюсь, но думаю не в этом случае =)
@@lambdaway Перечитал свой коммент, который был написан год назад и он мне показался надменным. Извините). Сейчас я уже не смогу вспомнить, что имел ввиду. Возможно я ошибся, а возможно нет. В тот момент, я читал книгу Кормена (она не совсем простая), и старался каждый алгоритм сортировки реализовывать и разбирать. Как будет время (не скоро), напишу ответ. Кстати, при разборе алгоритмов сортировки, я частенько обращался к вашим роликам. Спасибо!