In [1]:

    

L = 32
L_even = 16  
L_odd  = 15


    

In [ ]:

    

l = L_even
p = l // 2


    

In [2]:

    

[0,] + [1,2,3,4][:]


    

    
Out[2]:





[0, 1, 2, 3, 4]

In [3]:

    

X = range(5)


    

In [4]:

    

X


    

    
Out[4]:





[0, 1, 2, 3, 4]

In [5]:

    

X[:5]


    

    
Out[5]:





[0, 1, 2, 3, 4]

In [6]:

    

X[:4]


    

    
Out[6]:





[0, 1, 2, 3]

In [7]:

    

X[4]


    

    
Out[7]:





4

In [1]:

    

import os, sys
print(os.getcwd())


    

    




/home/topolo/PropD/CompPhys/crack/trees_arbres

In [2]:

    

sys.path.insert(0, os.getcwd())


    

In [3]:

    

from heaps import minHeap, maxHeap, minheapsort, maxheapsort


    

In [4]:

    

theHeap = minHeap()
theHeap.buildHeap([5,9,1,2,3])


    

    




(5, 6, 2)
([0, 5, 9, 1, 2, 3], 2)
([0, 5, 2, 1, 9, 3], 1)
([0, 1, 2, 5, 9, 3], 0)

In [5]:

    

print( theHeap.delMin() )


    

    




1

In [6]:

    

print(theHeap.heaplst, theHeap.size)
print( theHeap.delMin() )
print(theHeap.heaplst, theHeap.size)
print( theHeap.delMin() )
print(theHeap.heaplst, theHeap.size)
print( theHeap.delMin() )
print(theHeap.heaplst, theHeap.size)
print( theHeap.delMin() )


    

    




([0, 2, 3, 5, 9], 4)
2
([0, 3, 9, 5], 3)
3
([0, 5, 9], 2)
5
([0, 9], 1)
9

In [11]:

    

myHeap = minHeap()
myHeap.insert(9)
print(myHeap.heaplst,myHeap.size)
myHeap.insert(1)
print(myHeap.heaplst,myHeap.size)
myHeap.insert(5)
print(myHeap.heaplst,myHeap.size)


    

    




([0, 9], 1)
([0, 1, 9], 2)
([0, 1, 9, 5], 3)

In [12]:

    

print( myHeap.delMin() )
print(myHeap.heaplst, myHeap.size)


    

    




1
([0, 5, 9], 2)

In [13]:

    

myHeap.insert(2)
print(myHeap.heaplst,myHeap.size)
myHeap.insert(7)
print(myHeap.heaplst,myHeap.size)


    

    




([0, 2, 9, 5], 3)
([0, 2, 7, 5, 9], 4)

In [14]:

    

print( myHeap.delMin() )
print(myHeap.heaplst, myHeap.size)
print( myHeap.delMin() )
print(myHeap.heaplst, myHeap.size)


    

    




2
([0, 5, 7, 9], 3)
5
([0, 7, 9], 2)

In [15]:

    

myHeap = minHeap()
myHeap.buildHeap([9,1,8,1])
print(myHeap.size)
print(myHeap.delMin())
print(myHeap.heaplst,myHeap.size)


    

    




(4, 5, 2)
([0, 9, 1, 8, 1], 2)
([0, 9, 1, 8, 1], 1)
([0, 1, 1, 8, 9], 0)
4
1
([0, 1, 9, 8], 3)

In [16]:

    

print(myHeap.delMin())
print(myHeap.heaplst,myHeap.size)


    

    




1
([0, 8, 9], 2)

In [17]:

    

print(myHeap.delMin())
print(myHeap.heaplst,myHeap.size)


    

    




8
([0, 9], 1)

In [18]:

    

myHeap = minHeap()
myHeap.buildHeap([9,5,6,2,3])
print(myHeap.delMin())
print(myHeap.heaplst,myHeap.size)
print(myHeap.delMin())
print(myHeap.heaplst,myHeap.size)
print(myHeap.delMin())
print(myHeap.heaplst,myHeap.size)
print(myHeap.delMin())
print(myHeap.heaplst,myHeap.size)


    

    




(5, 6, 2)
([0, 9, 5, 6, 2, 3], 2)
([0, 9, 2, 6, 5, 3], 1)
([0, 2, 3, 6, 5, 9], 0)
2
([0, 3, 5, 6, 9], 4)
3
([0, 5, 9, 6], 3)
5
([0, 6, 9], 2)
6
([0, 9], 1)

In [4]:

    

print( minheapsort([9,5,6,2,3]) )


    

    




(5, 6, 2)
([0, 9, 5, 6, 2, 3], 2)
([0, 9, 2, 6, 5, 3], 1)
([0, 2, 3, 6, 5, 9], 0)
[2, 3, 5, 6, 9]

In [6]:

    

print( [2,3,5,6,8].reverse() )


    

    




None

In [7]:

    

class MaxHeap:
    """ @class MaxHeap
        @notes 
        given node i
        parent of i is i // 2
        p(i) = i / 2
        left child of i, l 
        l(i) = 2*i
        right child of i, r 
        r(i) = 2*i + 1 
        completely balanced tree, if i is parent, it can have no right child, but at least a left child 
        Consider total number of nodes N.  
        i=h= N/2 will be a parent 
        but N/2+1, N/2+2 are for sure children  
        max heap property: A(p(i)) >= A(i)
    """
    def __init__(self):
        self.A = [0] # 1-based counting
        self.N = 0 # L is size or length 
        
    def maxChild(self,i):
        l = 2*i
        r = 2*i+1
        N = self.N
        if (r > N): 
            return l
        else:
            if self.A[r] >self.A[l]:
                return r
            else:
                return l
    
    def percdown(self,i):
        l = 2*i
        N = self.N
        while( l<= N):
            mc = self.maxChild(i)
            if self.A[i] < self.A[mc]: # swap to enforce max heap property
                self.A[i], self.A[mc] = self.A[mc], self.A[i]
            i = mc
            l = 2*i
        
    def buildHeap(self,X):
        self.A = [0,] + X[:]
        L = len(X)
        self.N = L
        i = L//2 # very last parent, L/2+1, L/2+2 are leafs
        while ( i > 0):
            self.percdown(i)
            i=i-1
    
    def delmax(self):
        maxval = self.A[1]
        N = self.N
        self.A[1] = self.A[N] # 1-based counting
        self.A.pop()
        self.N = N-1
        self.percdown(1)
        
        return maxval


    

In [8]:

    

maxheap1 = MaxHeap()
maxheap1.buildHeap( [12,11,13,5,6,7])


    

In [9]:

    

print(maxheap1.N)
sortedlst = []
for _ in range(maxheap1.N):
    sortedlst.append( maxheap1.delmax() )


    

    




6

In [14]:

    

print(sortedlst)
print(list( reversed( sortedlst ) ) )


    

    




[5, 6, 7, 11, 12, 13]
[13, 12, 11, 7, 6, 5]

In [ ]: