우선순위 큐

class PQ:
    def __init__(self):
        self.pq = [-1 for _ in range(100)]
        self.length = 0

    def push(self,item):
        self.length += 1
        i = self.length
        p = i // 2

        while i != 1 and item<self.pq[p]:
            self.pq[i] = self.pq[p]
            i = p
            p = i//2

        self.pq[i] = item

    def pop(self):
        val = self.pq[1] #return 해야할 값
        item = self.pq[self.length] #마지막에 있는 애 꺼내서 위로 올렸다 가정.
        self.length -= 1 #길이 1 감소
        p = 1
        c = 2

        while c<=self.length:
            if c<self.length and self.pq[c]>self.pq[c+1]:
                c+=1
            if item<self.pq[c]:
                break
            self.pq[p] = self.pq[c]
            p = c
            c = c*2

        self.pq[p] = item

        return val

위 코드는 영남대 조행래 교수님 자료구조 수업을 참조한 코드이다.

5번째 보는 것 같은데 매우 아름다운 코드였다.

pop이나 push나 절차는 동일하다

1. 초기 부모와 자식 설정

2. 부모노드 또는 자식노드가 범위를 벗어나지 않을 때까지, 그리고 자식노드 값이 더 클때까지 반복한다.

3. 무엇을 반복? 부모와 자식노드의 교체작업을 반복한다.

4. 벗어났다면 비로소 관찰노드에 값을 입력한다.

push부분이 상대적으로 쉽게 느껴지는 것이 pop에 비해 push는 다음 비교 해야할 대상이 1개이다.

따라서 관심노드가 범위를 벗어나지 않거나(!= 1) 부모노드가 값이 더 클때까지 교체를 반복한다는게 쉽게 읽혀진다.

그에 비해 pop부분은 자식노드가 2개이므로

1. 왼쪽 자식노드가 범위 내 일 동안 반복
2. 두 자식 중 하나를 선택해야 하는데 오른쪽 자식노드를 선택하는 기준은 다음과 같다.
   • 왼쪽 자식노드가 self.length미만일 경우.
     • 왼쪽 자식노드가 self.length이면 오른쪽 자식노드는 존재하지 않기 때문
   • 오른쪽 자식 노드가 더 작을 경우.
     • 이는 priority queue의 알고리즘
3. 자식을 선택하고 나서야 비로소 pop처럼 자식노드가 값이 더 크다면 while문을 빠져나와준다.
4. 그게 아니라면 교체작업 반복
5. 벗어났다면 비로소 관찰노드에 값을 입력해준다.

처음 이 알고리즘을 접근했을 땐 왜이리 왔다갔다 하나 했는데 제대로 이해하지 못해서 이런 생각을 가졌던 것이다. 일관된 접근 아래에 매우 정교히 짜져 있었다. 역시 교수님~!