Автор оригинала: Python Examples.
В следующем примере мы реализовали алгоритм сортировки кучи. Кроме того, по умолчанию функция heap_sort () в следующей программе сортирует список в порядке возрастания. Чтобы получить порядок убывания, все, что вам нужно сделать, просто обратный список.
def heap_sort(alist): build_max_heap(alist) for i in range(len(alist) - 1, 0, -1): alist[0], alist[i] = alist[i], alist[0] max_heapify(alist, index=0, size=i) def parent(i): return (i - 1)//2 def left(i): return 2*i + 1 def right(i): return 2*i + 2 def build_max_heap(alist): length = len(alist) start = parent(length - 1) while start >= 0: max_heapify(alist, index=start, size=length) start = start - 1 def max_heapify(alist, index, size): l = left(index) r = right(index) if (l < size and alist[l] > alist[index]): largest = l else: largest = index if (r < size and alist[r] > alist[largest]): largest = r if (largest != index): alist[largest], alist[index] = alist[index], alist[largest] max_heapify(alist, largest, size) nlist = input('Enter the list of numbers separated by space\n').split() nlist = [int(x) for x in nlist] heap_sort(nlist) print('Sorted List after Heap Sort, in Ascending Order\n', nlist) nlist.reverse() print('Sorted List after Heap Sort, in Descending Order\n', nlist)
Enter the list of numbers separated by space 1 74 96 5 42 63 Sorted List after Heap Sort, in Ascending Order [1, 5, 42, 63, 74, 96] Sorted List after Heap Sort, in Descending Order [96, 74, 63, 42, 5, 1]