Max Heap insert function python

Question

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?

Line 2 and down. I don't know python, but I'm pretty sure those should be indented by one level. — Sergio Tulentsev, Nov 26 '21 at 11:27

score 1 · Accepted Answer · answered Nov 26 '21 at 13:25

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

Many thanks... but I have one more additional question: which will be more optimal to use this insertinmaxheap() function or just append the element to the list and then simply use heapify() method. — user123123, Dec 01 '21 at 07:43
The second method is more efficient if `heapify` is implemented with the bottom-up approach. See [How can building a heap be O(n) time complexity?](https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity) — trincot, Dec 01 '21 at 07:57

Max Heap insert function python

1 Answers1