decrease_weight 연산을 추가해 봅시다.
코드 13-11
def decrease_weight(self, new_elem): ➊
cur = self.pos[new_elem.v] ➋
while cur!= 1 and new_elem.w < self.arr[self.parent(cur)].w: ➌
self.arr[cur] = self.arr[self.parent(cur)] ➍
self.pos[self.arr[cur].v] = cur
cur = self.parent(cur)
self.arr[cur] = new_elem
self.pos[new_elem.v] = cur
➊ 프림 알고리즘을 위해 추가된 함수
➋ 업데이트될 정점의 현재 인덱스
➌ cur가 루트가 아니고 업데이트될 원소의 weight가 부모 원소의 weight보다 작다면 부모 원소를 아래로 내리고 cur가 루트 쪽으로 올라갑니다.
➍ 업데이트될 원소의 weight가 부모 원소의 weight보다 작다면 부모 원소를 한 칸 아래로 내립니다.
코드 13-11은 decrease_weight 연산을 구현한 것입니다. 매개변수로 기존보다 더 작은 가중치를 가진 에지가 전달됩니다. 이 에지에는 트리 밖 정점 v도 전달되겠지요. 이 정점 v가 저장된 arr의 원소로 찾아가 w와 _from을 업데이트하고 새롭게 업데이트된 w를 가지고 다시 정렬하면 됩니다. 최소 힙이기 때문에 w가 작아지면 자신의 부모와 가중치를 비교한 후 작다면 루트를 따라 올라가며 바꾸어야 하겠지요. 이는 마치 push 연산과 비슷합니다. 가장 중요한 코드는 메서드의 첫 번째 라인 cur=self.pos[new_elem.v]입니다. arr 내 현재 인덱스만 안다면 이 인덱스에 있는 w와 _from을 변경하고 w를 기준으로 부모 노드와 비교해서 w가 부모 노드의 w보다 작다면 최소 힙의 특성을 만족할 때까지 루트를 따라 올라가며 노드를 바꾸면 됩니다.
코드 13-11의 코드를 min_heap.py 파일에 담아 둡니다. 프림 알고리즘을 구현할 때 임포트할 것입니다. 다음 절에서는 프림 알고리즘을 구현해 봅시다.