3
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
1
  • \$\begingroup\$ informative, thanks \$\endgroup\$
    – minglyu
    Dec 6 '20 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.