Комментарии 6
Что это за поток мыслей? Почему два алгоритма сортировки описаны рядом с алгоритмом вычисления выпуклой оболочки? Как они связаны?
Зачем впилены номера строк с тире в псевдокоде? К ним нету никаких отсылок. Псевдокод на русском — та еще жесть, особенно на фоне других кусков псевдокода.
Помните, что даже если куча не будет полностью отсортирована, если мы построили нашу min-кучу правильно и без каких-либо ошибок, каждый отдельно взятый родительский узел в нашей куче будет меньше по значению, чем его дочерние элементы.
Это вообще как? Как можно не полностью отсортировать heap? Ну и чтобы при этом всем она еще и правильно построена была.
Как можно не полностью отсортировать heap?
Странный вопрос. Вообще-то он по определению не полностью отсортированный. У хипа только одна задача — наверху должен быть "самый-самый" элемент.
Насколько я помню, это не совсем так — главная особенность хипа — что любой родительский нод будет больше|меньше (соотв. для max-heap|min-heap) (или равен) любого из его детей.
In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete[1] tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.
Так что, да, наверху любого из нодов должен быть "самый-самый" элемент.
Пирамидальная сортировка упорядочена максимумом вперёд не просто так.
(Понятно, что всегда же можно проинвертировать порядок).
Дело в том, что это нужно исключительно для сортировки пирамидой, размещённой на массиве, вершиной вперёд!
Первый шаг — make_heap
В цикле:
- предусловие: [0..k) — это уже пирамида, [k..n) — ещё не обработанный хвост массива
- действие: берём элемент [k] и помещаем в пирамиду, которая прирастает на освободившееся место
- постусловие: [0..k+1) — пирамида, [k+1..n) — хвост
Второй шаг — sort_heap — и вот тут всё становится важным!
- предусловие: [0..k) — пирамида, [k..n) — уже упорядоченный хвост из максимумов
- действие: берём [0] — это очередной максимум (меньший хвоста, разумеется), удаляем его из пирамиды, освобождая [k], куда и кладём взятый элемент
- постусловие: [0..k-1) — пирамида, [k-1..n) — упорядоченный хвост
Если разместить пирамиду на массиве в обратном направлении, тогда там удобно будет хранить минимумом к вершине.
Ну а если мы делаем пирамидальную сортировку не на массиве по месту, а на списке и дереве, то, в зависимости от левого или правого фолда, пирамида должна держать минимум или максимум на вершине.
Очень странная солянка из алгоритмов. Без этого статья слишкмо короткая получалась?
Дожили, датасаентисты играют в псевдобейсик.
Циферки ещё бы канонично расставили, с шагом 10.
Если уж переводите статью, то переводите единообразно.
Почему в ваших "алгоритмах" половина идентификаторов переведена, а другая половина и все ключевые слова — нет?
Зачем изучать именно эту подборку алгоритмов?
Зачем именно в таком виде?
Зачем вам, компании ОТУС, понадобилось иллюстрировать ваш курс переводом какой-то стрёмной статьи?
Не хочу делать за вас вашу работу, но.
Я бы для начала обозначил предмет разговора.
Например, потребление памяти алгоритмами сортировки:
- линейное (mergesort — выделяем промежуточные массивы)
- логарифмическое (quicksort — стек рекурсии)
- константное (heapsort, insertions, bubble)
Пирамидальная сортировка, сортировка слиянием и выпуклая оболочка