Confusion about variables in python

Question

I am trying to implement heapsort but I am getting unexpected results. I think this is due to something I don't understand about how Python handles variables (I am talking about side effects). Here's the code:

from math import *

def parent(i):
    return floor((i+1)/2)-1

def left(i):
    return 2*i+1

def right(i):
    return 2*i+2

def maxheapify(A, i):
    l = left(i)
    r = right(i)
    if l < len(A) and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r < len(A) and A[largest] < A[r]:
        largest = r
    if largest != i:
        temp = A[i]
        A[i] = A[largest]
        A[largest] = temp
        maxheapify(A, largest) 


def buildmaxheap(A):
    for i in range(int(floor(len(A)/2)), -1, -1):
        maxheapify(A, i)

def heapsort(A):
    n = len(A)
    buildmaxheap(A)
    for k in range(len(A), 0, -1):  
        temp = A[0]
        A[0] = A[k-1]
        A[k-1] = temp
        C = A[0:k-1]
        maxheapify(C, 0)
        A = C + A[k-1:n]
    print(A)

Now when I run

A = [2, 4, 1, 3, 7, 5, 9]
heapsort(A)
print(A)

I obtain two printed lines (one from inside the heapsort showing that the sorting worked and one from the last print):

[1, 2, 3, 4, 5, 7, 9]
[1, 7, 5, 3, 4, 2, 9]

Obviously, I'd like them both to be the same (which would mean that the sorting actually worked and A is sorted after calling heapsort(A))

So what I don't get is:

If A is correctly sorted (at the point of the last line in heapsort(A)), why doesn't this change persist after leaving the function block?
If this is due to some permanence of the variable A, why isn't the end result the original value of A, but the intermediate step in heapsort, which is the result of the maxheapify call?

You can replace A = C + A[k-1:n] with A[0:k-1] = C in your code. The code in my answer below uses a similar technique. — Noctis Skytower
– Noctis Skytower, Commented Aug 25, 2016 at 13:23

Mark Ransom · Accepted Answer · 2016-08-24 21:16:18Z

2

At the start of the function, the list A inside the function is the same as the list outside of the function, and any modifications made to one will be reflected in the other (it's a mutable object).

When you do an assignment to a list, you're substituting a new list object for the old list object. This breaks the connection to the outside object.

Instead of assigning a new list to A, you can assign to a slice of A and the original object will be modified in place instead.

A[:] = C + A[k-1:n]

answered Aug 24, 2016 at 21:16

Mark Ransom

310k44 gold badges423 silver badges660 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sethmlarson · Accepted Answer · 2016-08-24 21:16:45Z

1

A = C + A[k-1:n]

This is the line responsible for the behaviour you're seeing. By setting A equal to A[0:k-1] + A[k-1:n] you are making a copy of all of A's elements. If you want your changes to persist within the list you passed in you must assign the list to all the elements of A like so:

A[:] = C + A[k-1:n]

answered Aug 24, 2016 at 21:16

sethmlarson

9511 gold badge8 silver badges22 bronze badges

Comments

Noctis Skytower · Accepted Answer · 2016-08-25 13:20:20Z

The following implementation shows a rewrite of your code but includes an alternate solution above the last call to the print function. The commented-out line may replace the line directly above it, or you may choose to return a at the end of the heap_sort function and rebind the value of a in your main function instead.

def main():
    a = [2, 4, 1, 3, 7, 5, 9]
    heap_sort(a)
    print(a)

parent = lambda i: (i + 1 >> 1) - 1
left = lambda i: (i << 1) + 1
right = lambda i: i + 1 << 1

def max_heapify(a, i, n):
    l = left(i)
    r = right(i)
    largest = l if l < n and a[i] < a[l] else i
    if r < n and a[largest] < a[r]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest, n)

def build_max_heap(a, n):
    for i in reversed(range(n + 2 >> 1)):
        max_heapify(a, i, n)

def heap_sort(a):
    n = len(a)
    build_max_heap(a, n)
    for k in reversed(range(n)):
        a[0], a[k] = a[k], a[0]
        c = a[:k]
        max_heapify(c, 0, k)
        a[:k] = c
        # the following would change "a" in this scope only
        # a = c + a[k:]
    # print(a)

if __name__ == '__main__':
    main()

Collectives™ on Stack Overflow

Confusion about variables in python

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related