1 """
   2 Este código es propiedad de Diego Andrés Sanabria y es liberado bajo licencia GPL v2.0
   3 """
   4 class Arbol:
   5     clave=None
   6     izq=None
   7     der=None
   8     raiz=None
   9     def __init__(self,niv=0):
  10         self.niv=niv
  11     def __actNiv__(self,niv=0):
  12         self.niv=niv
  13         if self.izq:
  14             self.izq.__actNiv__(self.niv+1)
  15         if self.der:
  16             self.der.__actNiv__(self.niv+1)
  17     def __tab__(self,n):
  18         a=""
  19         for i in range(n):
  20             a=a+"\t"
  21         return a
  22     def __repr__(self):
  23         a=""
  24         a=a+str(self.clave)+"\n"
  25         if self.izq!=None:
  26             a=a+self.__tab__(self.izq.niv)+"Izq:"
  27             a=a+str(self.izq)+"\n"
  28         if self.der!=None:
  29             a=a+self.__tab__(self.der.niv)+"Der:"
  30             a=a+str(self.der)
  31         return a
  32     def ordenar(self):
  33         if self.raiz!=None:
  34             if self.clave>self.raiz.clave:
  35                 tmp=self.raiz.clave
  36                 self.raiz.clave=self.clave
  37                 self.clave=tmp
  38                 self.raiz.ordenar()
  39     def ordenarabajo(self,dato):
  40         if self.izq!=None and self.der!=None:
  41             if self.izq.clave>self.der.clave:
  42                 self.clave=self.izq.clave
  43                 self.izq.ordenarabajo(dato)
  44             else:
  45                 self.clave=self.der.clave
  46                 self.der.ordenarabajo(dato)
  47         elif self.izq!=None and self.der==None:
  48             self.clave=self.izq.clave
  49             self.izq.ordenarabajo(dato)
  50         elif self.izq==None and self.der==None:
  51             self.clave=dato
  52 class Monticulo:
  53     def __init__(self):
  54         self.abierto=[]
  55         self.cerrado=[]
  56         self.arbol=Arbol()
  57         self.datotmp=None
  58     def insertar(self,dato):
  59         if self.arbol.clave==None:
  60             self.arbol.clave=dato
  61         else:
  62             self.abierto.append(self.arbol)
  63             while len(self.abierto)!=0:
  64                 tmp=self.abierto.pop(0)
  65                 try:
  66                     self.cerrado.index(tmp)
  67                 except:
  68                     self.cerrado.append(tmp)
  69                     if tmp.izq!=None:
  70                         self.abierto.append(tmp.izq)
  71                     else:
  72                         tmp.izq=Arbol()
  73                         tmp.izq.clave=dato
  74                         tmp.izq.raiz=tmp
  75                         tmp.izq.ordenar()
  76                         break
  77                     if tmp.der!=None:
  78                         self.abierto.append(tmp.der)
  79                     else:
  80                         tmp.der=Arbol()
  81                         tmp.der.clave=dato
  82                         tmp.der.raiz=tmp
  83                         tmp.der.ordenar()
  84                         break
  85             self.abierto=[]
  86             self.cerrado=[]
  87         self.arbol.__actNiv__()
  88     def atender(self):
  89         if self.arbol.clave!=None:
  90             self.abierto.append(self.arbol)
  91             while len(self.abierto)!=0:
  92                 tmp=self.abierto.pop(0)
  93                 try:
  94                     self.cerrado.index(tmp)
  95                 except:
  96                     self.cerrado.append(tmp)
  97                     if tmp.izq!=None:
  98                         self.abierto.append(tmp.izq)
  99                     if tmp.der!=None:
 100                         self.abierto.append(tmp.der)
 101             ult=self.cerrado.pop()
 102             pult=ult.raiz
 103             if pult.izq!=None and pult.der!=None:
 104                 self.datotmp=pult.der.clave
 105                 pult.der=None
 106                 self.arbol.ordenarabajo(self.datotmp)
 107             elif pult.izq!=None and pult.der==None:
 108                 self.datotmp=pult.izq.clave
 109                 pult.izq=None
 110                 self.arbol.ordenarabajo(self.datotmp)
 111             ult=None
 112         self.abierto=[]
 113         self.cerrado=[]
 114         self.arbol.__actNiv__()