Индексирование алгоритма сортировки кучи от Geeks для Geeks кажется мало - PullRequest
Новая
       6

Индексирование алгоритма сортировки кучи от Geeks для Geeks кажется мало

2 голосов
/ 12 февраля 2020

Просто быстрый вопрос. Я смотрел на алгоритм HeapSort от Geeks for Geeks в Python, и когда он строит maxheap с помощью функции heapSort, диапазон изменяется от (n, -1, -1), если не должно быть (n-1, -1 , -1)? Ниже приведен фрагмент кода 

# Python program for implementation of heap Sort 

# To heapify subtree rooted at index i. 
# n is size of heap 
def heapify(arr, n, i): 
    largest = i # Initialize largest as root 
    l = 2 * i + 1     # left = 2*i + 1 
    r = 2 * i + 2     # right = 2*i + 2 

    # See if left child of root exists and is 
    # greater than root 
    if l < n and arr[i] < arr[l]: 
        largest = l 

    # See if right child of root exists and is 
    # greater than root 
    if r < n and arr[largest] < arr[r]: 
        largest = r 

    # Change root, if needed 
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i] # swap 

        # Heapify the root. 
        heapify(arr, n, largest) 

# The main function to sort an array of given size 
def heapSort(arr): 
    n = len(arr) 

    # Build a maxheap. 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 

    # One by one extract elements 
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i] # swap 
        heapify(arr, i, 0)
...