Heap insertion and deletion Implementation using Python

Question

I have implemented basic max heap insertion and deletion functions without recursion

# insertion
arr: [6,5,4,3,2,1]

# insert 7
arr: [7,5,6,3,2,1,4]
tree:

        7   
    5       6
  3   2   1    4

# delete 7
arr: [6,5,4,3,2,1]
tree:

        6
    5       4
  3   2  1     

My implementation

def insert(arr,ele):
    # bottom up
    n = len(arr)
    # insert into the n+1 position
    new_arr = arr.append(ele)
    i = n # last position
    while True:
        p_index = int((i-1)/2)
        # compare with the parent index
        if (arr[i] > arr[p_index]):
            # swap the elements
            arr[p_index], arr[i] = arr[i], arr[p_index]
            i = p_index
        else:
            # correct
            break
    return arr

# deletion
def delete(arr):
    # top down
    if not arr:
        return None
    # swap the last elment to root
    arr[0], arr[len(arr)-1] = arr[len(arr)-1], arr[0]
    item = arr.pop()
    n = len(arr)
    i = 0 
    # comparing the children
    while True:
        # left/right child index
        lc_index = 2*i + 1
        rc_index = 2*i + 2
        # no chilren
        if lc_index > n-1:
            break
        # only has left child
        if lc_index == (n-1) and rc_index > n-1: 
            if arr[lc_index] > arr[i]:
                arr[i], arr[lc_index] = arr[lc_index], arr[i]
            break
        else:
            if arr[lc_index] > arr[rc_index]:
                arr[i], arr[lc_index] = arr[lc_index], arr[i]
                i = lc_index
            else:
                arr[i], arr[rc_index] = arr[rc_index], arr[i]
                i = rc_index
    return item

These two functions works fine, but looks pretty cumbersome especially the delete function, any suggestions how to improve the code?

Answer 1

Integer division

Are you using Python 3? If so, there is the integer division operator: //. Instead of:

    p_index = int((i-1)/2)

you can write:

    p_index = (i - 1) // 2

Unnecessary variable

In your insert function, where do you use n?

    n = len(arr)
    ...
    i = n # last position

Seems like you can get rid of the n variable, and just initialize i = len(arr)

Wrong variable

In delete, where do you use n?

You might say it is used in several places. I'd disagree. I'd say it is never used; you only use n-1.

What is n-1? It is the last index of the array:

    last = len(arr) - 1

    ...

    if lc_index > last:
        ...
    if lc_index == last and rc_index > last:
        ...

Unnecessary test:

Consider:

    lc_index = 2*i + 1
    rc_index = 2*i + 2

Note that we could rewrite that last statement as

    rc_index = lc_index + 1

Now consider:

    if lc_index == last and rc_index > last:
        ...

Substitute for rc_index ...

    if lc_index == last and lc_index + 1 > last:
        ...

If the first part of that test is True, the second part will always be True; if the first part is false, the second part will never be evaluated. So you just need:

    if lc_index == last:
        ...

Left or right?

The code for the left & right children look identical, save for the index being used.

Instead of:

        if arr[lc_index] > arr[rc_index]:
            arr[i], arr[lc_index] = arr[lc_index], arr[i]
            i = lc_index
        else:
            arr[i], arr[rc_index] = arr[rc_index], arr[i]
            i = rc_index

You could select the correct left or right index to use:

        child_index = lc_index if arr[lc_index] > arr[rc_index] else rc_index

Then you don't need two copies of the remaining code:

        arr[i], arr[child_index] = arr[child_index], arr[i]
        i = child_index

Last element

 arr[0], arr[len(arr)-1] = arr[len(arr)-1], arr[0]

The arr[len(arr)-1] references the last element of arr, by determining the length of the array, and subtracting one to compute the zero-based index.

Using arr[-1] also references the last element of the array, using Python's negative indexing feature. This allows a much simpler statement:

 arr[0], arr[-1] = arr[-1], arr[0]