Implementing heap sort algorithm in Python receiving recursion error when running

Question

Im trying to implement the heap sort algorithm to sort a list but receiving the following error code: RecursionError: maximum recursion depth exceeded Please let me know if you find any issues I will post my functions and helper functions below as follows:

def heap_sort(A):
    heap_size = _build_max_heap(A)
    for i in range(heap_size // 2, -1):
        A[0], A[i] = A[i],A[0]
        heap_size = heap_size - 1
        _max_heapify(A,heap_size, I)

def _build_max_heap(A):
    heap_size = len(A)
    for i in range(heap_size // 2):
        _max_heapify(A,heap_size, I)
    return heap_size

def _left(I):
    return (2*i)+1

def _right(i):
    return (2*i)+2

def _max_heapify(A, heap_size, i ):
     l = _left(i)
    r = _right(i)
    if l < heap_size and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r < heap_size and A[largest] < A[r]:
        largest = r
    if largest != i:
       A[i], A[largest] = A[largest], A[i]
    _max_heapify(A,heap_size, largest)

CryptoFool · Accepted Answer · 2022-09-24 00:38:42Z

3

Your problem is due to the fact that your _max_heapify function calls itself recursively, and it ALWAYS calls itself, no matter what is passed to it as parameters. For recursion to work, there has to be a condition that becomes true such that the recursive function doesn't call itself. You need to modify your logic so that this is the case...so that there is some condition that at some point halts the recursion by having an execution of _max_heapify that doesn't call itself.

answered Sep 24, 2022 at 0:38

CryptoFool

23.4k5 gold badges31 silver badges55 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Anon Over a year ago

Considering this, does the rest of my implementation look correct and once I figure out how to fix this issue, does my algorithm look like it will efficiently run? Also, is there anyway you can go into further depth specifying how I can go about making this change, I am relatively new to coding and recursion is not my strong suit.

CryptoFool Over a year ago

Well, your code has some syntax errors in it (see 'I' vs 'i'), so I wonder how you could have even gotten to the point where you got the recursion error. I see some big red flags in your code. For example, I don't understand why your heap_sort function calls _build_max_heap, which in terms calls _max_heapify a bunch of times, and then loops again, itself calling _max_heapify a bunch of times. I can't imagine how going through the looping and recursion twice can be the right thing to do.

Collectives™ on Stack Overflow

Implementing heap sort algorithm in Python receiving recursion error when running

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related