[알고리즘] 최대힙

문제

자신이 할 일에 우선순위를 매겨서 힙에 저장했다가 우선순위 순으로 꺼내서 출력하는 프로그램을 작성하여 보자. (python)

소스코드

class MaxHeap :
    def __init__ (self) :
        self.heap = []
        self.heap.append((0, ''))

    def size(self) : return len(self.heap) - 1
    def isEmpty(self) : return self.size() == 0
    def Parent(self, i) : return self.heap[i//2]
    def Left(self, i) : return self.heap[i*2]
    def Right(self, i) : return self.heap[i*2+1]
    def display(self, msg = '힙 트리: ') :
        print(msg, self.heap[1:])

    def insert(self, n, todo):
        self.heap.append((n,todo))
        i = self.size()
        while(i != 1 and n > self.Parent(i)[0]):
            self.heap[i] = self.Parent(i)
            i = i // 2
            self.heap[i] = (n, todo)
    def delete(self):
        parent = 1
        child = 2
        if not self.isEmpty():
            hroot = self.heap[1] # 삭제할 루트를 복사해둠
            last = self.heap[self.size()] # 마지막노드
            while (child <= self.size()): # 마지막노드이전까지
                if child<self.size() and self.Left(parent)[0] < self.Right(parent)[0]:
                    child += 1 # 만약 오른쪽이 더 크면 child를 1 증가
                if last[0] >= self.heap[child][0]:
                    break; # 마지막노드보다 더 큰 자식이 작으면 break
                self.heap[parent] = self.heap[child] #아니면 down-heap을 계속함
                parent = child
                child *= 2; #기본이 왼쪽자식노드
            self.heap[parent] = last #마지막노드를 parent에 복사
            self.heap.pop(-1) # 마지막노드삭제
            return hroot      # 저장한 루트 반환

heap = MaxHeap()

while(1):
    i_or_d = input("삽입(i), 삭제(d) : ")
    if i_or_d != 'i' and i_or_d != 'd':
        print("메뉴선택 다시 하세요")
        break
    if i_or_d == 'i':
        todo = input("할일: ")
        n = int(input("우선순위: "))
        heap.insert(n, todo)
    if i_or_d == 'd':
        print("제일 우선순위가 높은 일은 '%s'" % heap.delete()[1])

실행 결과