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]