Ali-Buch in Python: Selbstimplementierung der Prioritätswarteschlange

Ich habe versucht, die Praxis der Verwendung der Klasse so zu schreiben, wie ich es mir vorstellen kann, aber ist das wirklich O (log n)? (Die Geschichte, die Berechnungszeit richtig zu betrachten). Es sollte in aufsteigender Reihenfolge herauskommen.

Ich verwende hier und da Python-Standardlistenoperationen, daher ist es schade, dass es dort zu O (n) wird.

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())

Ich habe das Gefühl, dass es definitiv eine prägnantere Schreibweise gibt.

Nachtrag) Es scheint, dass die Standardvariable, die aus irgendeinem Grund in \ _ \ _ init \ _ \ __ eingefügt wurde, möglicherweise sehr gefährlich war (siehe Kommentar).

Mit Virtual Box + Ubuntu + Anaconda auf Python3.6 migriert.