CODEWITHSUNDEEP
pythonalgorithmsortingheap
Mercrist
Mercrist

Reputation: 109

HeapSort code works on smaller arrays but not bigger ones

def heapSort(arr, end):
    '''Heap Sort Algorithm'''
    '''Average Case: O(n*log(n))'''
    '''Worst Case: Θ(n*log(n))'''
    '''Best Case: Ω(n*log(n))'''
    if end <= 0 or len(arr) <= 1: #algorithm ends when there's one element or less
        return arr
    buildHeap(arr, end)
    arr[0], arr[end] = arr[end], arr[0]
    end -= 1
    return heapSort(arr,end)
    


def buildHeap(arr, end):
    '''Builds the Max Heap'''
    if end <=0: #recursively max heap half of arr to the start
        return arr

    i = (end-1)//2 #parent
    while i >= 0: #index backwards, swapping the parent with the bigger of each child 
        leftChild = 2*i+1
        rightChild = 2*i+2

        if arr[leftChild] > arr[rightChild] and arr[leftChild] > arr[i] and rightChild <= end: #make sure right child is within our end bounds
            arr[i], arr[leftChild] = arr[leftChild], arr[i]

        elif arr[rightChild] > arr[leftChild] and arr[rightChild] > arr[i] and rightChild <= end:
            arr[i], arr[rightChild] = arr[rightChild], arr[i]
        i-=1
    end-=1 
    return buildHeap(arr, end)
from random import randint
A = [randint(1,100) for i in range(20)]
print(A)
print(heapSort(A, len(A)-1))

Above is my following heap sort code, the error occurs in my buildHeap function (the if line(s)). On all initial runs the right child ends up being equals to the length of the array (not the length of the array-1), so the code goes out of index bounds. Weirdly enough, my Python implementation of the algorithm works for smaller lists. Any help on how to fix and/or improve my code?

Upvotes: 0

Views: 128

Answers (1)

trincot
trincot

Reputation: 350212

You are making the within-bounds check too late in the below statements, because by the time that check is made you already have referenced arr[rightChild]. You should first check -- as a guard -- and only then access arr[rightChild]. So replace:

if arr[leftChild] > arr[rightChild] and arr[leftChild] > arr[i] and rightChild <= end: #make sure right child is within our end bounds
    arr[i], arr[leftChild] = arr[leftChild], arr[i]

elif arr[rightChild] > arr[leftChild] and arr[rightChild] > arr[i] and rightChild <= end:
    arr[i], arr[rightChild] = arr[rightChild], arr[i]

With:

if arr[leftChild] > arr[i] and (rightChild > end or arr[leftChild] > arr[rightChild]): 
    arr[i], arr[leftChild] = arr[leftChild], arr[i]

elif rightChild <= end and arr[rightChild] > arr[i]:
    arr[i], arr[rightChild] = arr[rightChild], arr[i]

BTW, your heap building function is not very efficient. It has a time complexity of O(n²), using O(n) extra (stack) space, while this can be done in linear time and constant extra space, with Floyd's method.

Upvotes: 2

Related Questions