[자료구조] 우선순위 큐(Priority Queue) 와 힙(Heap) 알아보기

우선순위 큐

우선순위 속성을 가지는 큐

우선순위 큐는 배열, 연결 리스트, 힙으로 구현 할 수 있다.

힙 구현 방식이 시간 복잡도가 가장 낮기 때문에 힙으로 구현한다.(O(logN))

힙

힙 순서 속성을 가지는 완전 이진 트리(자유 저장소 힙이 아님)

 

힙의 삽입 연산

🐬 1 : 힙의 최고 깊이 가장 우측에 새 노드 추가.(완전 이진 트리 유지)

🐬 2 : 삽입한 노드를 부모 노드와 비교한다. 삽입한 노드가 부모 노드보다 크면 맞는 위치니 연산 종료.

🐬 3 : 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드의 위치를 교환. 교환 후 2번 - 3번 반복

 

 

예시

 

다음 힙에 값이 7인 노드를 삽입하는 예시다.

 

값이 7인 노드를 힙의 마지막에 추가하고 부모 노드와 비교한다.

7은 31보다 작으므로 이 두 노드를 교환한다.

한 단계 올라온 7과 7의 부모를 비교한다. 

7은 9보다 작으므로 두 노드를 교환한다.

7과 부모인 뿌리노드 를 비교한다.

뿌리노드 2가 더 작으므로 교환을 수행하지 않는다.

이렇게 노드 삽입이 종료 된다.

 

 

힙의 최솟값(뿌리 노드) 삭제 연산

🐬 1 : 힙의 마지막 노드를 뿌리 노드로 이동한다. (힙의 순서 속성 파괴, 재조정 필요)

🐬 2 : 옮겨온 노드의 양쪽 자식노드와 비교하여 작은 쪽 자식노드와 위치를 교환한다.

🐬 3 : 옮겨온 노드가 자식노드가 없거나 자식 노드 보다 작은 값을 가지면 연산을 종료한다. (아닐 경우 2번 - 3번 반복)

 

예시

루트 노드를 삭제하고 마지막 노드의 값을 루트 노드에 대입한다.

옮겨진 노드와 그 자식 노드를 비교하여 작은쪽과 교환한다.

자식 노드가 더 작지 않을때 까지 반복 한다.

자식 노드가 더 크므로 종료한다.

힙 의 값을 저장

 

깊이 n의 노드는 배열 2ⁿ-1 ~ 2*2ⁿ-2  번 인덱스에 저장된다.

또, k번 인덱스의 자식노드는 

왼쪽 : 2k + 1

오른쪽 : 2k + 2

힙 저장 하는 예시