Quiz
Do you think these assertions will pass?
values = [1, 2, 3]
class SortedList:
def __init__(self, values: list[int]):
self._values = values
def push(self, value: int):
self._values.append(value)
self._values.sort()
def peek(self) -> int:
return self._values[-1]
h1 = SortedList(values)
h2 = SortedList(values)
h1.push(5)
h2.push(6)
assert h1.peek() == 5
assert h2.peek() == 6
Answer
They fail.
assert h1.peek() == 5 # AssertionError: got 6 because both heaps share the same list.
Why?
In Python, mutable objects are shared by default.
Mutable objects are passed and assigned by reference, not copied.
We pass the same values list to two SortedList instances.
In each class, self._values shares that same list reference.
Tips:
We can use the list constructor to create a copy of the passed list.
values = [1, 2, 3]
class SortedList:
def __init__(self, values: list[int]):
self._values = list(values) # This creates a copy of `values`.
def push(self, value: int):
self._values.append(value)
self._values.sort()
def peek(self) -> int:
return self._values[-1]
h1 = SortedList(values)
h2 = SortedList(values)
h1.push(5)
h2.push(6)
assert h1.peek() == 5
assert h2.peek() == 6
The constructor builds a list whose items are the same and in the same order as iterable’s items. iterable may be either a sequence, a container that supports iteration, or an iterator object. If iterable is already a list, a copy is made and returned, similar to iterable[:].