Сортировка кучи в Python

Вступление

Heap Sort – еще один пример эффективного алгоритма сортировки. Его главное преимущество заключается в том, что он имеет большое наихудшее время выполнения O(n*log n) независимо от входных данных.

Как следует из названия, HeapSort в значительной степени опирается на структуру данных heap – распространенную реализацию очереди приоритетов .

Без сомнения, HeapSort-один из самых простых алгоритмов сортировки для реализации, и в сочетании с тем фактом, что это довольно эффективный алгоритм по сравнению с другими простыми реализациями, с ним часто приходится сталкиваться.

Сортировка кучи

Сортировка кучи работает путем “удаления” элементов из части кучи массива один за другим и добавления их в отсортированную часть массива. Прежде чем мы углубимся в объяснение и вернемся к структуре данных кучи, мы должны упомянуть несколько атрибутов самой сортировки кучи.

Это алгоритм in-place , означающий, что он требует постоянного объема дополнительной памяти, то есть необходимая память не зависит от размера самого исходного массива, кроме памяти, необходимой для хранения этого массива.

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

Сортировка кучи нестабильна , что означает, что она не поддерживает относительный порядок элементов с равными значениями. Это не проблема с примитивными типами (такими как целые числа и символы…), но это может быть проблемой, когда мы сортируем сложные типы, такие как объекты.

Например, представьте, что у нас есть пользовательский класс Person с полями age и name , и несколько объектов этого класса в массиве, включая человека по имени “Майк” в возрасте 19 лет и “Дэвид”, также в возрасте 19 лет, появляющихся в этом порядке.

Если бы мы решили отсортировать этот массив людей по возрасту, не было бы никакой гарантии, что “Майк” появится перед “Дэвидом” в отсортированном массиве, даже если они появились в этом порядке в исходном массиве. Это может случиться, но это не гарантировано.

Забавный факт: Сортировка кучи-это алгоритм сортировки выбора в ядре Linux

Структура Данных Кучи

Кучи – одна из самых популярных и широко используемых структур данных в информатике, не говоря уже о том, что она очень популярна во время интервью с программистами.

Мы будем говорить о кучах, отслеживающих наименьший элемент (min-heap), но они так же легко могут быть реализованы для отслеживания самого большого элемента (max-heap).

Проще говоря, min-heap-это древовидная структура данных, в которой каждый узел меньше всех его дочерних узлов. Чаще всего используется двоичное дерево. Кучи имеют три поддерживаемые операции – delete_minimum() , get_minimum () и add() .

Вы можете только удалить первый элемент в куче, после чего он “прибегает”. Кучи “прибегают” сами после того, как элемент добавлен или удален, так что самый маленький элемент всегда находится в первой позиции.

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

Давайте рассмотрим пример кучи:

Как мы видим, приведенный выше пример подходит под описание кучи, но не сортируется. Мы не будем вдаваться в подробности реализации кучи, так как это не является предметом нашей статьи. Решающим преимуществом структуры данных кучи, которую мы используем при ее использовании в HeapSort, является то, что следующий наименьший элемент всегда является первым элементом в куче .

Примечание: Благодаря тому, как кучи сортируют элементы после удаления элемента, сложность перемещения следующего наименьшего элемента на первую позицию, сохраняя при этом массив в куче, занимает O(logn) время, что является высокоэффективной операцией.

Реализация

Сортировка Массивов

Python предоставляет методы для создания и использования куч, поэтому нам не нужно реализовывать их самостоятельно:

heappush(list, item) : Добавляет элемент в кучу и использует его позже, чтобы он оставался кучей. Может использоваться в пустом списке.
heappop(list) : Всплывает (удаляет) первый (самый маленький) элемент и возвращает этот элемент. Куча остается кучей после этой операции, поэтому нам не нужно вызывать heapify() .
heapify(list) : Превращает данный список в кучу. Стоит отметить, что этот метод существует, хотя мы не будем его использовать, так как не хотим изменять наш исходный массив.

Теперь, когда мы это знаем, реализация сортировки кучи довольно проста:

from heapq import heappop, heappush

def heap_sort(array):
    heap = []
    for element in array:
        heappush(heap, element)

    ordered = []

    # While we have elements left in the heap
    while heap:
        ordered.append(heappop(heap))

    return ordered

array = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2]
print(heap_sort(array))

Выход:

[2, 4, 5, 13, 15, 17, 18, 21, 24, 26]

Как мы видим, тяжелая работа выполняется с помощью структуры данных кучи, все, что нам нужно сделать, это добавить все необходимые элементы и удалить их один за другим. Это почти как машина для подсчета монет, которая сортирует введенные монеты по их стоимости, а затем мы можем их вынуть.

Сортировка Пользовательских Объектов

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

Однако, поскольку наша реализация опирается на встроенные методы кучи, мы не можем сделать это здесь.

Python предоставляет следующие методы:

heapq.nlargest(*n*, *iterable*,*) : Возвращает список с n наибольшими элементами из набора данных, определенного iterable .
heapq.nsmallest(*n*, *iterable*,*) : Возвращает список с n наименьшими элементами из набора данных, определенного iterable .

Который мы могли бы использовать, чтобы просто получить n(массив) наибольшие/наименьшие элементы, но сами методы не используют сортировку кучи и по существу эквивалентны простому вызову метода sorted () .

Единственное решение, которое мы оставили для пользовательских классов, – это фактически переопределить операторы сравнения. Это, к сожалению, ограничивает нас только одним типом сравнения для каждого класса. В нашем примере это ограничивает нас сортировкой объектов Movie по годам.

Тем не менее, это позволяет нам продемонстрировать использование сортировки кучи на пользовательских классах. Давайте продолжим и определим класс Movie :

from heapq import heappop, heappush

class Movie:
    def __init__(self, title, year):
        self.title = title
        self.year = year

    def __str__(self):
        return str.format("Title: {}, Year: {}", self.title, self.year)

    def __lt__(self, other):
        return self.year < other.year

    def __gt__(self, other):
        return other.__lt__(self)

    def __eq__(self, other):
        return self.year == other.year

    def __ne__(self, other):
        return not self.__eq__(other)

А теперь давайте немного изменим нашу функцию heap_sort() :

def heap_sort(array):
    heap = []
    for element in array:
        heappush(heap, element)

    ordered = []

    while heap:
        ordered.append(heappop(heap))

    return ordered

И, наконец, давайте создадим несколько фильмов, поместим их в массив, а затем отсортируем:

movie1 = Movie("Citizen Kane", 1941)
movie2 = Movie("Back to the Future", 1985)
movie3 = Movie("Forrest Gump", 1994)
movie4 = Movie("The Silence of the Lambs", 1991);
movie5 = Movie("Gia", 1998)

array = [movie1, movie2, movie3, movie4, movie5]

for movie in heap_sort(array):
    print(movie)

Выход:

Title: Citizen Kane, Year: 1941
Title: Back to the Future, Year: 1985
Title: The Silence of the Lambs, Year: 1991
Title: Forrest Gump, Year: 1994
Title: Gia, Year: 1998

Сравнение с другими алгоритмами сортировки

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

Основным преимуществом HeapSort здесь является верхняя граница O(n*logn) с точки зрения временной сложности и безопасности. Разработчики ядра Linux приводят следующие доводы в пользу использования сортировки кучи по QuickSort:

Время сортировки кучи составляет O(n*logn) как в среднем, так и в худшем случае. Хотя qsort в среднем работает примерно на 20% быстрее, он страдает от эксплуатируемого наихудшего поведения O(n*n) и дополнительных требований к памяти, которые делают его менее подходящим для использования ядром.

Кроме того, Быстрая сортировка плохо ведет себя в предсказуемых ситуациях, и при достаточном знании внутренней реализации она может создать угрозу безопасности (в основном DDoS-атаки), так как bad O(n ² ) поведение может быть легко вызвано.

Другой алгоритм , с которым часто сравнивают HeapSort, – это сортировка слиянием, которая имеет ту же временную сложность.

Сортировка слиянием имеет то преимущество , что она стабильна и интуитивно распараллеливается , в то время как сортировка кучи не является ни тем, ни другим.

Еще одно замечание заключается в том, что сортировка кучи в большинстве случаев медленнее, чем сортировка слиянием, даже если они имеют одинаковую сложность, поскольку сортировка кучи имеет большие постоянные коэффициенты.

Однако сортировка кучи может быть реализована гораздо проще на месте , чем сортировка слиянием, поэтому она предпочтительнее, когда память является более важным фактором, чем скорость.

Вывод

Как мы видели, HeapSort не так популярен, как другие эффективные алгоритмы общего назначения, но его предсказуемое поведение (кроме нестабильности) делает его отличным алгоритмом для использования там, где память и безопасность важнее, чем немного более быстрое время выполнения.

Это действительно интуитивно понятно реализовать и использовать встроенную функциональность, предоставляемую Python, все, что нам по сути нужно сделать, это положить предметы в кучу и вынуть их- подобно счетчику монет.