Comments 7
Спасибо за подробный разбор, есть ли какие то бенчмарки, чем этот алгоритм лучше других, скорость/память?
Строить предположения только оценке временной сложности О, сегодня и последние несколько десятилетий, мне кажется некорректным. Я не нашел когда этот метод начали использовать, но судя по всему, процессоры в то время еще не были суперскалярными, а память была одна и работала на частоте процессора, не было, ни кеша, ни дисков и прочего. Сегодня быстрей может работать не тот алгоритм у кого лучше О, а тот, при котором предсказатель ветвления будет меньше ошибаться или тот кто, будет более оптимально работать с кешем. И это только два фактора из многих, которые будут влиять на скорость, но которые к сожалению мало кто учитывает.
Строить предположения только оценке временной сложности О, сегодня и последние несколько десятилетий, мне кажется некорректным. Я не нашел когда этот метод начали использовать, но судя по всему, процессоры в то время еще не были суперскалярными, а память была одна и работала на частоте процессора, не было, ни кеша, ни дисков и прочего. Сегодня быстрей может работать не тот алгоритм у кого лучше О, а тот, при котором предсказатель ветвления будет меньше ошибаться или тот кто, будет более оптимально работать с кешем. И это только два фактора из многих, которые будут влиять на скорость, но которые к сожалению мало кто учитывает.
Алгоритм вполне известный и в следующем году отпразднует своё сорокалетие, наверное, кто-то где-то когда-то делал тесты, замеры… И это ещё нужно чтобы была в наличии оптимизированная версия сортировки, тот питоновский код что приведён в статье скорее демонстративный, чем подходящий для реальных задач.
Странный, на мой взгляд, термин — куча куч, скорее уж это стек (или связный список) куч.
Стек куч — очень удачный термин применительно к рассматриваемой ситуации. Я, во всяком случае, возьму его в использование применительно к подобным структурам.
Куча куч тоже вполне уместно звучит. Обратите внимание, что если в этом векторе куч взять размеры всех куч, то получим невозрастающую последовательность (или неубывающую, если двигаться по списку куч в обратном направлении). То есть, если смотреть не на значения элементов в корнях, а на количество узлов каждой кучи, то в этом контексте имеем дело тоже именно с кучей (частный случай бинарного дерева, у которого от корня идёт только одна ветка, однако отсутствует вторая — такое тоже допустимо для кучи). Так как узлы представляют из себя невозрастающую последовательность, то выполняется условия сортирующего дерева — каждый потомок больше (если это min-heap) чем родитель.
Куча куч тоже вполне уместно звучит. Обратите внимание, что если в этом векторе куч взять размеры всех куч, то получим невозрастающую последовательность (или неубывающую, если двигаться по списку куч в обратном направлении). То есть, если смотреть не на значения элементов в корнях, а на количество узлов каждой кучи, то в этом контексте имеем дело тоже именно с кучей (частный случай бинарного дерева, у которого от корня идёт только одна ветка, однако отсутствует вторая — такое тоже допустимо для кучи). Так как узлы представляют из себя невозрастающую последовательность, то выполняется условия сортирующего дерева — каждый потомок больше (если это min-heap) чем родитель.
С коде есть ошибка, после сортировки некоторые значения расположены в неправильном порядке. Это так и было задумано?
Sign up to leave a comment.
Плавная сортировка