蟻本をpythonで: プライオリティキューの自力実装

クラスを使う練習もかねてとりあえず思いつく方法で書いてみたものの、これは本当にO(log n)なんだろうか (計算時間をちゃんと見ろという話)。一応小さい順にはでてくるようにはなっているはず。

python標準のリスト操作をちらほら使っているのでそこでO(n)になってたりすると残念なことに。

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

絶対にもっと簡潔な書き方がある気がする。

追記) なぜか__init___に入れてしまっていたデフォルト変数が潜在的に非常に危険だった模様(コメント参照)。

Virtual Box + Ubuntu + Anacondaでpython3.6へ移行。