heap enhancements

[Peter Otten]

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