Priority Queue, heap ( 우선순위큐, 힙 )

✔️ Priority Queue(우선순위 큐)

◾ 우선순위 큐는 큐와 비슷하다.

◾ 큐는 연산의 결과로 "먼저 들어간 데이터가 먼저 나온다." 하지만 우선순위 큐의 연산 결과는 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다."

◾ 우선순위 큐는 배열, 연결리스트, 힙을 이용하여 구현할 수 있다.

◾ 배열기반으로 우선순위 큐를 구현하면, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시키면 된다.

◾ 하지만 삽입&삭제 연산에서의 shift 연산 오버헤드가 발생한다. 또한 적절한 삽입 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위 비교를 진행해야할 수도 있다.

◾ 연결리스트 기반으로 우선순위 큐를 구현하면, 배열과 같이 shift 오버헤드는 발생하지 않지만 우선순위에 따른 적절한 삽입 위치를 찾아야하는 단점은 똑같다.

◾ 배열과 연결리스트 기반 우선순위큐의 단점으로 인해 우선순위 큐는 힙이라는 자료구조를 이용해서 구현하는 것이 일반적이다.

 

✔️ Heap(힙)

◾ 힙은 완전 이진트리 자료구조이다. 그리고 모든 노드에 저장된 값은 자식노드에 저장된 값보다 크거나 같아야 한다. 즉 Root 노드에 저장된 값이 가장 커야한다.

◾ Root 노드로 올라갈수록 저장된 값이 커지는 완전 이진트리를 Max Heap(최대힙)이라고 부른다.

◾ 반면, Root 노드로 올라갈 수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 Min Heap(최소힙)이라고 부른다.

◾ 힙은 완전 이진 트리이면서, 어느 위치에서든 다음 식이 성립한다. "자식 노드 데이터의 우선순위 <= 부모 노드 데이터의 우선 순위"

◾ 영단어 Heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 지닌다. 

◾ Heap은 우선순위 큐는 동일한 것이 아니다. 힙은 우선순위 큐 구현에 딱 어울리는, 완전 이진 트리의 일종이다.

 

💭동작과정

◾ 데이터 삽입 : 데이터를 삽입한 후에도 힙 구조를 유지해야한다! 삽입할 새로운 데이터는 우선순위가 제일 낮다는 가정하에서 '마지막 위치'에 삽입한다. 그리고는 부모노드와 우선순위를 비교해서 위치가 바뀌어야 한다면, 바꾼다. 이후에도 적절한 위치를 찾을때까지 계속해서 부모노드와 비교한다. '마지막 위치'는 노드를 추가한 이후에 완전 이진 트리가 유지되는, 마지막 레벨의 가장 오른쪽 위치를 뜻한다. 

 

◾ 데이터 삭제 : 우선 순위가 가장 큰 루트 노드를 삭제한다. (삭제 후에도 당연히 힙의 구조를 유지해야한다.) '마지막 노드'를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게한다. '마지막 노드'는 완전 이진 트리에서 마지막 레벨의 가장 오른쪽에 위치한 노드를 뜻한다. 

 

 

⏱️시간복잡도

◾ 데이터의 우선순위가 높을수록 데이터를 배열의 앞쪽에 위치시키는 방식으로 구현한 우선 순위 큐의 성능은 다음과 같이 정리할 수 있다.

 

- 배열 기반 데이터 저장의 시간 복잡도 : O(N)

- 배열 기반 데이터 삭제의 시간 복잡도 : O(1)

 

◾ 연결리스트 기반 우선 순위 큐도 마찬가지이다.

 

- 연결리스트 기반 데이터 저장의 시간 복잡도 : O(N)

- 연결리스트 기반 데이터 삭제의 시간 복잡도 : O(1)

 

◾ 힙을 기반으로 하면 트리의 높이에 해당하는 수만큼만 비교연산을 수행하면 된다.

 

- 힙 기반 데이터 저장의 시간 복잡도 : O(logN)

- 힙 기반 데이터 삭제의 시간 복잡도 : O(logN)

 

👀 시각화

Heap 시각화

💾 소스 코드