Если вы хотите увидеть, как heapsort может быть реализован в Python, посмотрите не дальше, чем стандартный библиотечный модуль heapq.В Python есть реализации heapsort как на C, так и на Python, а модуль heapq определяет Python, а затем перезаписывает их (если они есть) на C.Это означает, что вы можете прочитать и понять реализацию Python, но получите преимущество версии C, если вы действительно ее используете.
В конце приведен краткий пример использования модуля:
heap = []
data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
for item in data:
heappush(heap, item)
sort = []
while heap:
sort.append(heappop(heap))
print sort
Куча представлена частично отсортированным списком, который имеет ограничение, которое для каждого элемента с индексом n в списке имеет отношение heap[n] <= heap[n*2+1] and heap[n] <= heap[n*2+2] (игнорируя элементы, которые не существуют).Это простой способ свернуть двоичное дерево в простой список для удобства хранения.
heappush() помещает новый элемент в список, сохраняя этот инвариант, heappop() удаляет наименьший элемент.heapify(somelist) переупорядочивает список на месте для удовлетворения инварианта.
heapsort очень полезен, когда вы хотите отсортировать только часть списка (дайте мне наименьшее k элементов), или где вы хотите обработатьмельчайшие предметы при постоянном получении новых предметов, которые попадают в список.Хорошим примером последнего может служить планировщик задач операционной системы, в котором вы сохраняете кучу выполняемых потоков в порядке приоритетов и можете быстро вытаскивать выполняемый поток с наивысшим приоритетом из кучи всякий раз, когда вам нужно запланировать запуск потока.
Редактировать : Есть несколько причин, по которым список / массив более подходит для хранения кучи, чем явная древовидная структура.Наиболее очевидные из них - это то, что у явного дерева больше накладных расходов на память (либо с указателями внутри каждого объекта, либо с отдельным объектом, который должен быть выделен для каждого объекта в куче), но и оно медленнее, чем всякий раз, когда объект перемещается в вашей кучеобновить несколько указателей на детей и, возможно, родителей.
Чуть менее очевидным является то, что вам нужно иметь возможность легко получить последний элемент, который легко найти в списке, но это также означает, что вам также необходимо хранить и обновлять одноуровневый элемент.указатели на каждый элемент.Причина, по которой вам нужно иметь возможность легко получить последний элемент, состоит в том, что для добавления элемента вы делаете его последним элементом, а затем переупорядочиваете его по отношению к его родителю и элементу (операция O (log n)) или удаляете элемент.Наименьший вы просто помещаете текущий последний элемент на его место и меняете порядок вниз.Если у вас нет O (1) доступа к последнему элементу дерева, то обе эти операции плохо влияют на производительность.