# Heap insertion and deletion Implementation using Python

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?

# 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.

        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]

• informative, thanks – minglyu Dec 6 '20 at 20:25