How to divide an heap into two sub-heap with heapify for heapsort?

Question

i'm triyng to create an HeapSort function in python, using some auxiliar functions.

I'm trying to follow my book instructions, and using some functions like fixHeap which restore the right order in an heap with a node not following rules:

def getMaxKnot(i,j,A):
    k = max(A[i],A[j])
    if k==A[i]:
        return i
    if k==A[j]:
        return j


def fixheap(v,H): #basically restore an heap with a node not following heap rules
    if (2*v+1)>len(H)-1:
        return H
    else:
        u=getMaxKnot(2*v+1,2*v+2,H)
        if H[u]>H[v]:
            listoperations.swap(u,v,H) #swap item in position u and v
        return fixheap(u,H)

Now, i want basically to create a heapify function which works recursively on left-tree and right-tree, using my function fixheap to restore the right order.

My idea was the following:

def heapify(A):
        if A==[]:
            return A
        else:
            heapify(LEFT TREE)
            heapify(RIGHT TREE)
            fixheap(0,A)

Any ideas on how to divide my Array A into LEFT TREE and RIGHT TREE?

Answer 1

First, there is something missing in fixheap. Imagine that the node v only has one (left) child, then getMaxKnot will trigger an invalid index error, because j would point beyond the end of the A array.

Personally, I don't think getMaxKnot deserves to be a separate function. I would also put the arguments of fixheap in the opposite order, so that the second one can be easily omitted and given a default value (when it is the root element). Also swapping two values is really a one-liner:

def fixheap(H, v = 0): # put arguments in this order
    u = 2*v + 1
    if u >= len(H):
        return H
    if u+1 < len(H) and H[u+1] > H[u]: # Only compare when there are two child nodes
        u += 1
    if H[u] > H[v]:
        [H[u], H[v]] = [H[v], H[u]] # Swapping is easy
        return fixheap(H, u)

Then to your main question: your heapify should also get a node as argument, which would be the root of the subtree you want to heapify. The principle is in fact not much different from how the fixheap function is used:

def heapify(H, v = 0):
    u = 2*v + 1
    if u >= len(H):
        return H
    heapify(H, u)
    if u + 1 < len(H): # make sure there is a right child
        heapify(H, u+1)
    fixheap(H, v)