Кодирование heapsort для python 3
def heapSort(lst):
heap = arrayHeap.mkHeap(len(lst), arrayHeap.less)
alst = list(lst)
while alst != []:
v = alst.pop(0)
arrayHeap.add (heap, v)
while heap.size != 0:
w = arrayHeap.removeMin(heap)
alst.append(w)
return last
это действительная функция сортировки кучи?
1 ответ
Предполагая ваш arrayHeap
предоставляет те же гарантии, что и stdlib heapq
или любая другая разумная реализация кучи, тогда это допустимая сортировка кучи, но это очень глупо.
Скопировав исходную последовательность в список, а затем щелкнув с левой стороны, вы делаете O(N^2) подготовку к вашей сортировке O(N log N).
Если вы измените это на всплывающее с правой стороны, то вы только делаете подготовку O(N), поэтому все это занимает O(N log N), как это должно быть в heapsort.
При этом я не могу понять, почему вы хотите выскочить из списка, а не просто перебирать его. Или, если на то пошло, почему вы хотите скопировать оригинальную последовательность в список, а не просто перебирать ее напрямую. Если вы сделаете это, это будет быстрее, и будет использовать только половину памяти, и будет намного проще кода. Как это:
def heapSort(lst):
heap = arrayHeap.mkHeap(len(lst), arrayHeap.less)
for v in lst:
arrayHeap.add(heap, v)
alst = []
while heap.size:
w = arrayHeap.removeMin(heap)
alst.append(w)
return last
С немного более приятным API, как в stdlib heapq
модуль (кстати, почему вы его не используете?), вы можете сделать это еще проще:
def heapSort(lst):
alst = []
for v in lst:
heapq.heappush(alst, v)
return [heapq.heappop(alst) for i in range(len(alst))]
... или, если вы уверены lst
это список, и вы не против его поменять:
def heapSort(lst):
heapq.heapify(lst)
return [heapq.heappop(lst) for i in range(len(lst))]
... или, конечно, вы можете скопировать lst
и затем измените копию:
def heapSort(lst):
alst = lst[:]
heapq.heapify(alst)
return [heapq.heappop(alst) for i in range(len(alst))]
Вы можете заметить, что первый из них является первым из основных примеров в heapq
Docs.