Livre Ali en python: Auto-implémentation de la file d'attente prioritaire

J'ai essayé d'écrire la pratique d'utilisation de la classe d'une manière à laquelle je pourrais penser, mais est-ce vraiment O (log n)? (L'histoire de regarder correctement le temps de calcul). Il devrait sortir par ordre croissant.

J'utilise des opérations de liste standard python ici et là, c'est donc dommage que cela devienne O (n) là-bas.

def heapsort_one_step(heaplist,child_pos):
    if child_pos == 0:
        return heaplist,0,-1
    child = heaplist[child_pos]
    parent_pos = (child_pos-1)//2
    parent = heaplist[parent_pos]
    if parent > child:
        heaplist[child_pos], heaplist[parent_pos] = parent,child
        return heaplist,parent_pos,1
    else:

        return heaplist,parent_pos,-1

def heapsort(heaplist):
    a = 1
    child_pos = len(heaplist)-1
    while a != -1:
        heaplist,child_pos,a = heapsort_one_step(heaplist,child_pos)
    return heaplist


def reconstruct_heap_one_step(heaplist,parent_pos):

    if len(heaplist) == 2:
        heaplist = [min(heaplist),max(heaplist)]
        return heaplist, parent_pos, -1
        
    if 2*parent_pos+2 > len(heaplist)-1:
        return heaplist, parent_pos,-1
    
    child1 = heaplist[2*parent_pos + 1]
    child2 = heaplist[2*parent_pos + 2]

    if child1 > child2:
        minchild = child2
        child_pos = 2*parent_pos + 2
    else:
        minchild = child1
        child_pos = 2*parent_pos + 1

    if heaplist[parent_pos] > minchild:
        heaplist[child_pos], heaplist[parent_pos] = heaplist[parent_pos],heaplist[child_pos]
        return heaplist, child_pos,1
    else:
        return heaplist,child_pos,-1

def reconstruct_heap(heaplist):
    a = 1
    parent_pos = 0
    while a != -1:
        heaplist, parent_pos, a = reconstruct_heap_one_step(heaplist,parent_pos)
    return heaplist
        

class Heapq:

    def __init__(self,data = []):
        self.data = data

    def push(self,x):
        self.data.append(x)
        self.data = heapsort(self.data)
        print(self.data)

    def top(self):
        return self.data[0]

        
    def pop(self):
        if len(self.data) !=0:
            popval= self.data[0]
            self.data[0] = self.data[-1]
            self.data = self.data[:-1]
            self.data = reconstruct_heap(self.data)
            return popval
        else:
            print("Queue is empty.")

        


queue = []
x = Heapq(queue)

import random

for i in range(10):
    x.push(random.randint(0,100))

print(x.data)


for i in range(10):
    print(x.pop())

J'ai le sentiment qu'il existe définitivement une manière d'écrire plus concise.

Addendum) Il semble que la variable par défaut qui a été placée dans \ _ \ _ init \ _ \ __ pour une raison quelconque était potentiellement très dangereuse (voir commentaire).

Migré vers python3.6 avec Virtual Box + Ubuntu + Anaconda.