Вступление

Сортировка кучи - еще один пример эффективного алгоритма сортировки. Его главное преимущество состоит в том, что он имеет отличное время выполнения O (n * logn) в худшем случае независимо от входных данных.

Как следует из названия, Heap Sort в значительной степени полагается на структуру данных кучи - распространенную реализацию Priority Queue .

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

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

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

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

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

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

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

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

Интересный факт: Heap Sort - это предпочтительный алгоритм сортировки в ядре Linux.

Структура данных кучи

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

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

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

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

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

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

{.ezlazyload}

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

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

Выполнение

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

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

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

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

 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*, *key=None*) : возвращает список с n наибольшими элементами из набора данных, определенного с помощью iterable .
• heapq.nsmallest(*n*, *iterable*, *key=None*) : возвращает список с n наименьшими элементами из набора данных, определенного с помощью iterable .

Что мы могли бы использовать, чтобы просто получить n = len(array) наибольший / наименьший элемент, но сами методы не используют сортировку кучи и по сути эквивалентны простому вызову метода 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 

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

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

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

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

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

Другой алгоритм, с которым часто сравнивают Heap Sort, - это Merge Sort , который имеет такую же временную сложность.

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

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

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

Заключение

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

Реализовать и использовать встроенные функции, предоставляемые Python, действительно интуитивно понятно, все, что нам, по сути, нужно сделать,

• это сложить элементы в кучу и вынуть их - аналогично счетчику монет.