The following code counts the number of comparisons made by fuseSubheaps (which has the same role as the "restore heap" or "reheap" function in Heapsort). fuseSubheaps takes as input a positive integer and two (max)heaps. It creates a new heap from these by pushing down the label from the root (according to need) until it is placed in the correct position. When I print the result (as in the code), I get 2. It should be 4 (on the included test-case). When I print the partial results, 4 does appear but does not get printed. Rather than a code error, I suspect that this is due to the way Python prints from a recursion. I am trying to adapt the print command such that it produces the correct result.
def fuseSubheaps(arr, n, i, comparisoncount):
positionlargest = i # start the process at node i,
#comparisoncount keeps track of number of comparisons
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# Check if left child of root exists and its value is
# greater than root-value. Record position of largest value if so.
if l<n:
comparisoncount += 1
if arr[positionlargest] < arr[l]:
positionlargest = l
print(comparisoncount)
# Check if right child of root exists and its value is
# greater than root-value. Record position of largest value if so.
if r < n:
comparisoncount += 1
if arr[positionlargest] < arr[r]:
positionlargest = r
# swap root-value with largest value (at child) in case largest value resides
# at a child
print(comparisoncount)
if positionlargest != i:
arr[i], arr[positionlargest] = arr[positionlargest], arr[i] # swap
# Recursively call fuseSubheaps on the affected sub-tree
# after this swap
fuseSubheaps(arr, n, positionlargest,comparisoncount)
return comparisoncount
def outcomeFuseSubheaps(arr,n,i,comparisoncount):
a = fuseSubheaps(arr,n,i,comparisoncount)
print(a)
outcomeFuseSubheaps([1,4,3,2,7,6,5],7,0,0)```
