LeetCode
Anonymous
Python
07/25/2024 3:49 PM
1.7 KB
34
Indexable
Never
class Heap:
def __init__(self, lista):
self.data = []
for e in lista:
self.add(e)
def __len__(self)->int:
return len(self.data)
def add(self, e):
self.data.append(e)
if len(self)==1:
return
pos = len(self)-1
pos_padre = (pos-1)//2 #posición del padre
while pos>0 and e<self.data[pos_padre]:
self.data[pos]=self.data[pos_padre] #intercambio
pos= pos_padre #ir al padre
pos_padre = (pos-1)//2 #posición del padre
self.data[pos]=e
def pop(self):
if len(self)==0:
raise Exception('Nada que borrar')
salida = self.data[0]
if len(self)==1:
return self.data.pop()
self.data[0] = self.data.pop() # el último al primero
pos = 0
izq = 2*pos+1
der = 2*pos+2
# mientras sea peor que alguno...
while (izq < len(self) and self.data[pos]>self.data[izq]) or (der<len(self) and self.data[pos]>self.data[der]):
# va al izquierdo si solo hay ese o el izquierdo es el mejor
if der>=len(self) or self.data[izq]<self.data[der]:
self.data[pos], self.data[izq] = self.data[izq], self.data[pos]
pos = izq
else: # al derecho
self.data[pos], self.data[der] = self.data[der], self.data[pos]
pos = der
izq = 2*pos+1
der = 2*pos+2
return salida
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
h = Heap(nums)
salida = []
while len(h)>0:
salida.append(h.pop())
return salidaEditor is loading...
Leave a Comment