heap enhancements
Peter Otten
__peter__ at web.de
Sat Jan 4 10:04:13 EST 2020
jezkator at gmail.com wrote:
> ok, so it could be like this?
Easy things to improve:
(1) Avoid iterating over indices.
Wrong:
for i in range(len(stuff)):
item = stuff[i]
...
Better:
for item in stuff:
...
(1a) If you need the index use enumerate():
for i, value in enumerate(stuff)
if value < 0: stuff[i] = -value
(1b) Instead of modifiying a container it is often more convenient to build
a new one
stuff = [abs(v) for v in stuff] # common way
stuff = list(map(abs, stuff)) # also possible
(2) Test for "truthiness" rather than object identity
Wrong:
if x is True:
...
Better:
if x:
...
(3) Avoid toplevel code, or at least move it to the end of the script and
guard it with
if __name__ == "__main__": ...
Wrong:
do stuff
def foo(): ...
do more stuff
class Bar:
...
do even more stuff
Better
def foo(): ...
class Bar: ...
def main():
do stuff
do more stuff
do even more stuff
if __name__ == "__main__":
main()
(4) Choose names carefully.
> def checking(chain):
The function name should tell what is checked, e. g.
def is_valid_int(text):
(5) Parameterize your code to simplify tests and refactoring.
Wrong:
> chain = sys.stdin.read().splitlines()
> array_z = list()
> for line in chain:
> row=list(map(str, line.split()))
> array_z.append(row)
> #every line in input changes into 2D array
Better:
def read_2d_array(instream):
"""Read whitespace-separated pairs from `instream`.
Returns a list of 2-tuples.
pairs = []
for line in instream:
pair = line.split()
if len(pair) != 2:
raise ValueError
pairs.append(pair)
return pairs
array_z = read_2d_array(sys.stdin)
If you later decide to support files the change is obvious:
filename = ...
if filename == "-":
array_z = read_2d_array(sys.stdin)
else:
with open(filename) as instream
array_z = read_2d_array(instream)
(Somewhat advanced: read_2d_array() could also be a generator yielding
pairs.)
> def checking(chain):
> "checking if characters are numbers or not"
> for char in chain:
> if char not in "0123456789-":
> return False
> return True
This check is tedious and incomplete as it allows "-" in arbitrary
positions. Instead of testing the string for correctness before you convert
it it is often more convenient to try the conversion and cope with the
exception that may be raised. Instead of
# this is called "look before you leap", or LBYL
if is_valid_int_string(some_string):
intval = int(some_string)
else:
handle error
# "it's easier to ask for forgiveness than permission", or EAFP
try:
intval = int(s)
except ValueError:
handle error
-
> class MaxHeap:
> def __init__(self):
> """heap __init__ constructor"""
> self.heap =[]
> def bubble_up(self, i):
> """"bubble the element up if condition is ok """
> while i > 0:
> j = (i - 1) // 2
> if self.heap[i] <= self.heap[j]:
> break
> self.heap[j], self.heap[i] = self.heap[i], self.heap[j]
> i = j
> def insert(self, k):
> """insert element in heap"""
> self.heap += [k]
> self.bubble_up(len(self.heap) - 1)
> def peek(self):
> """return the biggest element"""
> return self.heap[0]
> def size(self):
> """return quantity of elements in heap"""
> return len(self.heap)
> def is_empty(self):
> """is heap empty?"""
> return self.size() == 0
The pythonic replacement for size() and is_empty() is
def __len__(self):
return len(self.heap)
You can then replace
myheap = MaxHeap()
print(myheap.size())
if myheap.is_empty(): print("myheap is empty")
with
print(len(myheap))
if not myheap: print("myheap is empty")
> def bubble_down(self, i):
> """bubble down the element"""
> n = self.size()
> while 2 * i + 1 < n:
> j = 2 * i + 1
> if j + 1 < n and self.heap[j] < self.heap[j + 1]:
> j += 1
> if self.heap[i] < self.heap[j]:
> self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
> i = j
> def pop(self):
> """delete the biggest element and change the heap"""
> element = self.heap[0]
> self.heap[0] = self.heap[-1]
> self.heap.pop()
> self.bubble_down(0)
> return element
>
> for i in range (len( array_z)):
> for j in range (len( array_z[i])):
> digit_z= array_z[i][j]
> if digit_z.isdigit() is True:
> array_z[i][j]=int( array_z[i][j])
> check =checking(digit_z)
> if check is True:
> array_z[i][j]=int( array_z[i][j])
>
> Heap=MaxHeap()
> for a in range (len( array_z)):
> if array_z[a][0]>0:
> Heap.insert( array_z[a])
> if array_z[a][0] < 0:
> print( array_z[a][1]+": ",end="") #print name of delivery
> index_of_package= array_z[a][0]
> while index_of_package<0 and (Heap.is_empty()) is False:
> delivery_package=Heap.pop()
> print(delivery_package[1],end=" ") #print name of package in
> delivery index_of_package+= 1
> print("")
> print("Depo: ",end="")
> while (Heap.is_empty()) is False:
> depo_package=Heap.pop()
> print(depo_package[1],end=" ") #print name of package in depo
More information about the Python-list
mailing list