источник:stack abuse.com/heap-sort-i…
Автор: Оливера Попович.
Перевод: Лао Ци
вводить
Heapsort — еще один пример эффективного алгоритма сортировки, и его главное преимущество заключается в том, что время его выполнения в наихудшем случае составляет O(n*logn) независимо от входных данных.
Как следует из названия, сортировка кучей в значительной степени зависит от структуры данных кучи — распространенной реализации приоритетных очередей.
Нет никаких сомнений в том, что сортировка кучей является простым алгоритмом сортировки, и по сравнению с другими простыми реализациями сортировка кучей более эффективна и распространена.
сортировка кучей
Heapsort работает, «удаляя» элементы один за другим из кучи и добавляя их к отсортированному массиву.Прежде чем объяснять и пересматривать структуру данных кучи, мы должны понять некоторые свойства самой heapsort.
Это алгоритм на месте (Примечание переводчика: алгоритм на месте, большинство из которых переводится как «алгоритм на месте», а некоторые также переводятся как «алгоритм на месте». Этот алгоритм представляет собой алгоритм, использующий небольшой фиксированный объем дополнительной памяти для преобразования данных. ), то есть требуется постоянный объем памяти, т. е. требуемая память зависит не от размера самого исходного массива, а от памяти, необходимой для хранения этого массива.
Например, нет необходимости ни в копии исходного массива, ни в рекурсии и стеках рекурсивных вызовов. Простейшая реализация сортировки кучей обычно использует второй массив для хранения отсортированных значений. Мы будем использовать этот подход, потому что он более интуитивно понятен и его проще реализовать в коде, но он также на 100 % работает на месте.
Heapsort нестабилен, что означает, что одинаковые значения не находятся в одном и том же относительном порядке. Для базовых типов, таких как целые числа, строки и т. д., таких проблем не возникает, но при сортировке объектов сложных типов мы можем столкнуться с ними.
Например, допустим, у нас есть пользовательский классPersonс участиемageиnameСвойства, несколько экземпляров этого класса в массиве, например 19-летний по имени «Майк» и 19-летний по имени «Дэвид» по порядку.
Если мы решим отсортировать этих людей по возрасту, нет никакой гарантии, что «Майк» появится перед «Дэвидом» в отсортированном массиве, даже если они появились в этом порядке в исходном массиве. Возможно, что «Майк» придет раньше «Дэвида», но это не гарантируется на 100%.
структура данных кучи
Куча — одна из самых популярных и часто используемых структур данных в информатике.Не говоря уже о том, что он очень популярен на собеседованиях по разработке программного обеспечения..
Мы поговорим о кучах, которые отслеживают самые маленькие элементы (min-heaps), но их также можно легко реализовать для отслеживания самых больших элементов (max-heaps).
Проще говоря, мини-куча — это древовидная структура данных, в которой каждый узел меньше, чем все его дочерние элементы. Обычно используется бинарное дерево. Куча имеет три основные операции:delete_minimum(),get_minimum()иadd().
Каждый раз вы можете удалить только первый элемент в куче, а затем «переупорядочить» его. После добавления или удаления элементов куча «переупорядочивает» себя так, что наименьший элемент всегда находится в первой позиции.
Примечание. Это никоим образом не означает, что куча представляет собой отсортированный массив. Тот факт, что каждый узел меньше своих дочерних элементов, недостаточен для того, чтобы гарантировать, что вся куча находится в порядке возрастания.
Давайте рассмотрим пример с кучами:
Как видим, приведенный выше пример подходит под описание кучи, но упорядочения нет. Мы не будем подробно обсуждать реализацию кучи, так как это не является предметом этой статьи. При использовании структур данных кучи в сортировке кучи мы используем ключевое преимущество структур данных кучи: следующий наименьший элемент всегда является первым элементом кучи.
выполнить
сортировка массива
Примечание переводчика:В этой статье автор не делает строгого различия между списками и массивами в Python, а рассматривает списки как массивы, что понятно, поскольку элементы в списке имеют один и тот же тип. Для сортировки это имеет смысл только для элементов одного типа.
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*, *key=None*): возвращает список, содержащийiterablen самых больших элементов в определенном наборе данных. -
heapq.nsmallest(*n*, *iterable*, *key=None*): возвращает список, содержащийiterableN наименьших элементов в определенном наборе данных.
Мы можем использовать это, чтобы просто получитьn = len(array)max/min, но сам метод не использует пирамидальную сортировку, что эквивалентно простому вызову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 широко используется, в основном из-за его надежности, хотя его часто превосходит хорошо зарекомендовавший себя метод «quicksort» (Примечание переводчика:Публичный аккаунт WeChat этой статьи «Laoqi Classroom» представляет различные алгоритмы сортировки в серии статей и реализует их на языке Python, так что следите за обновлениями).
Основными преимуществами сортировки кучей являются верхняя граница O(n*logn) временной сложности и безопасности. Разработчики ядра Linux привели следующие причины использования пирамидальной сортировки вместо быстрой:
Среднее время сортировки и наихудшее время сортировки кучи равныO(n*logn), хотя средняя скорость qsort на 20% выше, приходится терпетьO(n*n)наихудший сценарий и дополнительные накладные расходы памяти, что делает его менее подходящим для использования в ядре операционной системы.
Кроме того, алгоритм быстрой сортировки плохо работает в предсказуемых ситуациях. И, если вы достаточно знаете о внутренней реализации, вы можете знать о рисках безопасности, которые она представляет (в основном DDoS-атаки), потому что плохиеO(n^2)Поведение легко запускается.
Другим алгоритмом, который часто сравнивают с сортировкой кучи, является алгоритм сортировки слиянием (Примечание переводчика:Этот общедоступный аккаунт WeChat также будет публиковать соответствующие статьи для ознакомления, так что следите за обновлениями), они имеют одинаковую временную сложность.
Преимущество сортировки слиянием заключается в том, что она стабильна и может работать параллельно, в то время как сортировка кучи не может выполнять и то, и другое.
Еще одно замечание: даже при одинаковой сложности пирамидальная сортировка в большинстве случаев медленнее, чем сортировка слиянием, потому что у пирамидальной сортировки большой постоянный коэффициент.
Однако сортировку кучей легче реализовать, чем сортировку слиянием, поэтому она предпочтительнее, когда память важнее скорости.
в заключении
Как мы видели, heapsort не так популярен, как другие эффективные алгоритмы общего назначения, но его предсказуемое поведение (а не беспорядочное поведение) делает его хорошим алгоритмом для памяти и безопасности немного лучше, чем там, где важнее быстрая скорость работы.
Реализация и использование встроенной функциональности, предоставляемой Python, очень интуитивно понятна, все, что нам на самом деле нужно сделать, — это поместить элементы в кучу и извлечь их, как мы сделали со счетчиком монет.
Обратите внимание на публичный аккаунт WeChat: Lao Qi Classroom. Читайте подробные статьи, получайте превосходные навыки и наслаждайтесь блестящей жизнью.