할 일이 정해졌습니다. 최소 우선순위 큐를 만들어야 합니다. 우선순위 큐는 최소 힙(min heap)으로 구현하지요. 이전에 배운 알고리즘을 이용하여 최소 힙을 구현해 보겠습니다. 그런데 우리가 예상하지 못한 문제점이 하나 있습니다. 그것은 w_list를 업데이트해야 하는 상황이 있다는 것입니다. 어떤 상황에서 업데이트를 하게 될까요? 트리의 정점 집합이 자라면서 현재 알고 있던 가중치가 가장 작은 에지보다 더 가중치가 작은 에지를 발견했을 때입니다. 그때는 힙 안에 이미 있는 가중치가 더 작아지도록 업데이트해야 합니다. 그런데 아직까지 배운 알고리즘으로는 이를 구현할 수 없습니다. 이에 최소 힙에 decrease_weight 연산을 추가하겠습니다. 이는 가중치가 더 작은 에지를 최소 힙에 삽입하여 기존 가중치를 업데이트하는 연산입니다.

어떤 프로그래머들은 프림 알고리즘만을 위해 최소 힙 자료 구조 자체를 다시 구현해야 한다는 것에 불만이 많을 것입니다. 이미 잘 쓰는 바퀴를 다시 발명해야 하니 말입니다. 그래서 자료 구조를 처음부터 다시 구현하지 않고 기존에 있는 최소 힙 자료 구조를 이용하되 프림 알고리즘 내에서 약간의 트릭을 활용하는 편을 더 좋아합니다. 프림 알고리즘에서는 decrease_weight 연산을 직접 구현하는 형태로 최소 힙을 다시 구현할 것입니다. 기존 최소 힙 자료 구조를 이용하는 두 번째 방법은 프림과 매우 유사한 데이크스트라 알고리즘에서 구현해 보겠습니다.

decrease_weight 연산을 지원하려면 업데이트하려는 정점 v가 현재 최소 힙의 표현인 동적 배열의 어느 인덱스에 있는지 알아내야 합니다. 그래야만 해당 정점 요소에서 키 값으로 쓰는 가중치 값을 줄일 수 있습니다. 이를 위해 내부에 정점 v의 배열 내 위치를 저장해 두는 pos라는 배열을 따로 두겠습니다. 이제 코드로 구현해 보겠습니다.²