I wrote this insertion function for a max-heap:

def insertinmaxheap(arryhp, num):
    arryhp.append(num)
    arryhp.insert(0, 0)
    l = len(arryhp) - 1
    b = True
    while b:
        print(arryhp)
        print(l)
        print(int(l/2))
        if num <= arryhp[int(l / 2)] or int(l/2) < 2:
            b = False
        arryhp[l] = arryhp[int(l/2)]
        arryhp[int(l/2)] = num
        l = int(l/2)
    return arryhp[1:len(arryhp)]

I've tested it fore some values and it worked most of the time, but for this example it failed:

 insertinmaxheap([50, 30, 20, 15, 10, 8, 16], 19) 

The output is [50, 19, 20, 30, 10, 8, 16, 15], and as you can see 19 shouldn't be there.

What is wrong with this code?

CodePudding user response：

There are two problems:

• After b has been set to False the swap is still executed before exiting the loop. Execution should break out of the loop with break. This also makes the boolean b unnecessary.

• The condition int(l/2) < 2 should be int(l/2) < 1, as really the parent at index 1 should be compared with.

Other remarks:

• Make use of the integer division operator instead of flooring the floating point division.

• When you slice until the end, using 1:len(arryhp), you can omit the part after the colon: 1:.

• It is not nice that the returned list is not the mutated list that was given as argument. Either the input list should not be mutated, or the list that is returned is the mutated input list. The latter can be done by popping the first value out of the list with .pop(0).

Here is the code with those changes:

def insertinmaxheap(arryhp, num):
    arryhp.append(num)
    arryhp.insert(0, 0)
    l = len(arryhp) - 1
    while True:
        if num <= arryhp[l // 2] or l // 2 < 1:
            break
        arryhp[l] = arryhp[l//2]
        arryhp[l // 2] = num
        l = l // 2
    arryhp.pop(0)
    return arryhp

Now, this is not efficient. The insertion and popping of that dummy value is killing the time complexity of this algorithm. You should better not insert that dummy value and use the appropriate expression to determine the parent/child relationship.

Also, you don't have to assign num to the new slot in the heap in every iteration of the loop. It is enough to do this once, after the loop finishes and the final destination of num has been determined:

def insertinmaxheap(arryhp, num):
    arryhp.append(num)
    l = len(arryhp) - 1
    while l > 0:
        parent = (l - 1) // 2
        if num <= arryhp[parent]:
            break
        arryhp[l] = arryhp[parent]
        l = parent
    arryhp[l] = num
    return arryhp