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 salida
Editor is loading...
Leave a Comment