CODEWITHSUNDEEP
recursionheapsort
FrostyStraw
FrostyStraw

Reputation: 1656

How does the recursion work in heap-sort?

Let's say I have an array A = <1,6,2,7,3,8,4,9,5> pseudocode for Heapsort:

BUILD-MAX-HEAP(A)
n = A.heapsize = A.length
for i = floor(n/2) down to 1
   MAX-HEAPIFY(A,i)

MAX-HEAPIFY(A,i)
n = A.heap-size
l = LEFT(i)
r = RIGHT(i)
if l <= n and A[l] > A[i]
   largest = l
if r <= n and A[r] > A[largest]
   largest = r
if largest != i
   exchange A[i] <-> A[largest]
   MAX-HEAPIFY(A,largest)

I know BUILD-MAX-HEAP will first call MAX-HEAPIFY(A,4), which will exchange 7 and 9, then after MAX-HEAPIFY (A,3) it will switch 8 and 2. Then it will call MAX-HEAPIFY(A,2), and this is where I get confused. This is how the heap looks when MAX-HEAPIFY(A,2) is called

The first thing that will happen is that 6 and 7 will be exchanged, then it will call MAX-HEAPIFY(A,4) (because 4 is now largest), and exchange 6 and 9, then it will call MAX-HEAPIFY(A,8) but nothing will happen because you've reached a leaf, so then it returns to the function that called it.

MAX-HEAPIFY(A-8) was called by MAX-HEAPIFY(A,4) so it returns to it

MAX-HEAPIFY(A,4) was called by MAX-HEAPIFY(A,2) so it returns to it

but now A[2] < A[4] (because 7 < 9), and it is at this point that I wonder how it knows to call MAX-HEAPIFY(A,2) again to exchange 7 and 9. When a recursive function (or subroutine) returns to the one that called it, there is no more code to be executed (since MAX-HEAPIFY only calls MAX-HEAPIFY at the end of the function), so it will return back up the recursion stack and in my mind it feels like 7 will still be the parent of 9

Sorry if this is confusing, but can somebody walk me through this to help me understand how exactly this is recursively max-heapifying itself?

Upvotes: 2

Views: 4208

Answers (1)

Gerrat
Gerrat

Reputation: 29730

The following is the series of steps I get when following your algorithm (note the levels of indent when we recurse at the end of each). Every time we exit the function, we just return to the main program (calling max_heapify with the numbers 4 down to 1). I'm not positive where your interpretation is off, but I'm hoping the following makes it clearer.

for i in (4,3,2,1):
    MAX-HEAPIFY(A,i)

MAX-HEAPIFY(A,4):
    largest=4  # initialized
    l=8
    r=9
    largest=8  # calculated
    swap A[4] and a[8]:
    A = <1,6,2,9,3,8,4,7,5>
    MAX-HEAPIFY(A, 8):
        largest=8  # initialized
        l=16
        r=17
        ...return
    ...return

MAX-HEAPIFY(A,3):
    largest=3  # initialized
    l=6
    r=7
    largest=6  # calculated
    swap A[3] and A[6]:
    A = <1,6,8,9,3,2,4,7,5>
    MAX-HEAPIFY(A, 6):
        largest=6
        l=12
        r=13
        ...return
    ...return

MAX-HEAPIFY(A,2):
    largest=2 # initialized
    l=4
    r=5
    largest=4 # calculated
    swap A[2]and A[4]:
    A = <1,9,8,6,3,2,4,7,5>
    MAX-HEAPIFY(A, 4):
        largest=4  # initialized
        l=8
        r=9
        largest=8
        swap A[4] and A[8]:
        A = <1,9,8,7,3,2,4,6,5>
        MAX-HEAPIFY(A, 8):
            largest=8  # initialized
            l=16
            r=17
            ...return
        ...return
     ...return

MAX-HEAPIFY(A,1):
    largest=1  # initialized
    l=2
    r=3
    largest=2  # calculated
    swap A[1] and A[2]:
    A = <9,1,8,7,3,2,4,6,5>
    MAX-HEAPIFY(A, 2):
        largest=2:  # initialized
        l=4
        r=5
        largest=4:  # calculated
        swap A[2] and A[4]:
        A = <9,7,8,1,3,2,4,6,5>
        MAX-HEAPIFY(A, 4):
            largest=4:  # initialized
            l=8
            r=9
            largest=8:  # calculated
            swap A[4] and A[8]:
            A = <9,7,8,6,3,2,4,1,5>
            MAX-HEAPIFY(A, 8):
                largest=8:  # initialized
                l=16
                r=17        
                ...return
            ...return
        ...return
    ...return

Done!
A = <9,7,8,6,3,2,4,1,5>

I then went so far as to translate your algorithm (almost directly) into python (note I had to make a few tweaks for python's 0-based index):

def build_max_heap(A):
    for i in range(len(A)//2, 0, -1): 
        max_heapify(A, i)

def left(x):
    return 2 * x

def right(x):
    return 2 * x + 1


def max_heapify(A, i):
    n = len(A)
    largest = i
    l = left(i)
    r = right(i)
    if l<=n and A[l-1] > A[i-1]:
        largest = l
    if r <=n and A[r-1] > A[largest-1]:
        largest = r
    if largest !=i:
        A[i-1], A[largest-1] = A[largest-1], A[i-1]
        max_heapify(A,largest)

if __name__ == '__main__':
    A = [1,6,2,7,3,8,4,9,5]
    build_max_heap(A)  # modifies in-place
    print(A)

This prints: [9, 7, 8, 6, 3, 2, 4, 1, 5] (which agrees with our manual iterations)

...and for one more check, using python's heapq module with its private method _heapify_max:

import heapq
A = [1,6,2,7,3,8,4,9,5]
heapq._heapify_max(A)
print(A)

...prints the same: [9, 7, 8, 6, 3, 2, 4, 1, 5]

Upvotes: 1

Related Questions