우선순위 큐

이전에 힙 트리라는 자료구조에 대해 알아보았다.
 
우선순위 큐는 이 힙 트리를 이용한 자료구조인데...
 
간단하게 우선순위가 있는 애가 맨 첫번째로 나가는 자료구조이다!
 
힙 트리는 최상위(root)에 가장 큰 놈이 있으니까 root를 빼는 방식
 

이제 '우선순위 큐' 를 구현해보자.
 

List (힙 트리의 제약조건으로 List를 Tree로 사용할 수 있다)
 
List로 데이터를 받고 
 
힙트리의 제약조건중 부모가 커야하니까 들어온 데이터를 내 부모와 비교한다. (현재 - 1) / 2가 부모가 된다는 사실은 전에 보았으니 생략.
 
그리고 내가 더 크다면 부모와 나를 교체하는 방식으로 끝까지 올라가도록 반복!
 
Dequeue 도 구현해보면 결국 힙의 제약조건으로 인해 0번째 인덱스가 제일 큰 수라는것을 알 수 있기에 과감히 빼낸다.
 

근데 여기서 중요한 사실은, List로 구현을 하였기에 Remove를 0번째로 하면 곤란한 상황이 발생한다.
 
첫 번째가 빠져버리니 나머지 데이터가 앞으로 오기위해서 연산을 하니 문제!
 
그래서, 맨 앞칸을 지우지 않고 마지막 값을 첫 번째에 옮겨두고 마지막을 지우는 형태로 구현
 
이제 마지막이 맨 앞으로 왔으니 다시 구조를 잡기위해서 아래로 내려가며 비교를 한다!
 
자신의 왼쪽과 아랫쪽도 이전에 한 바가 있으니 생략하고 left, right중 더 큰 값을 찾아서 교체한다.
 
만약 next와 now가 같다면 그것은 결국 now가 제 위치에 있다는것을 알고
 
break를 통해서 나와준다.
 
 
이제 테스트를 해 보면...

 
값을 순서대로 넣지 않았는데 힙 트리의 구조를 가져 Enqueue가 제대로 진행됨을 알 수 있다. 
 

근데? Dequeue 가 무언가 잘못되었다.
 

Dequeue에서 비교를 하는 부분이 now가 아니라 next가 들어가야 한다.. 왜냐면 두개중 제일 큰 수를  찾는것이니까!

now가 들어가면 결국 밑에있는 right만 next가 되니까 문제 발생... 해결 완료!

 

우선순위 큐는 굉장히 빠르다. 왜냐하면 Enqueue와 Dequeue 시 모든 데이터를 검사하는게 아니라 자신의 부모 혹은 자식만 검사를 하면 되기에 결국 Tree의 높이만큼을 순회한다고 할 수 있다.

 

 

즉 데이터는 2의 제곱만큼 증가하는데 높이는 1씩 증가하니 이것은 Log²(N) 이라고 표현할 수 있다.

 

그래서 힙 트리를 사용한 우선순위 큐의 시간복잡도는 O(log₂(N)) 이라고 할 수 있다.