[javascript] 우선순위 큐 (1)

해당 포스팅은 큐와 트리를 이해했다는 가정하에 작성되고 있습니다. 큐와 트리에 이해도가 없는 분들은 본 포스팅을 보기 전 큐와 트리에 대한 포스팅을 먼저 읽어주시기 바랍니다. 

 

우선순위 큐란 ? 

 

 

우선순위 큐는 일반적인 큐와 거의 동일하다. 큐는 해당자료구조에 들어온 순서대로 배출이 된다. 다만 우선순위 큐는 우선순위큐는 먼저나가는 순서를 들어온 순서 뿐만 아니라 다른 조건에 의하여 들어온 데이터에 우선순위를 부여해 순위에 맞게 배출한다. 어찌보면 일반적인 큐도 우선순위큐가 될 수 있는데 배출되는 순서를 해당 큐에 들어온 순서에 의거하여 우선순위를 부여하여 배출하기 때문이다. 

 

우선순위 큐의 사용 예

 

우선순위 큐는 우리의 일상에서도 친근하게 사용되고 있다. 유니버셜 스튜디오랜드같은 해외 외국 놀이공원에서는 일반적인 티켓과 vip티켓, 더 높은 vvip티켓을 판매한다. 놀이기구를 타려면 줄을 서서 기다려야 하지만 vip나 vvip고객들은 특별통로를 이용하여 일반적인 티켓이용자들보다 훨씬 빨리 앞으로 갈 수 있다. 또한 vip와 vvip, 일반이용자가 동시에 기다리고 있으면 vvip, vip, 일반이용자 순으로 놀이기구를 탈 수 있다. 

 

우선순위큐의 구현방법

우선순위큐를 구현하는 방법으로는 배열과 링크드리스트,히프를 사용하는 방법이있다. 그리고 배열과 링크드리스트는 세부적으로 정렬되지 않았을 때와 정렬되었을 때의 두가지 방법으로 나뉜다. (히프는 다음 포스팅에서 따로 다룰 예정이다. )

 

정렬되지않았을 때

 

 

삽입 : 해당 배열의 끝에 데이터를 저장하면 되기에 삽입시의 시간 복잡도는 O(1)이 된다. 

배출 : 해당 배열에서 우선순위가 가장 높은 아이템을 배출해야하기 때문에 시간 복잡도는 O(n)이 된다.

(다만 배출시에는 삭제한 아이템 뒤에 있는 아이템들을 삭제한 위치까지 옮겨야 하기에 최악의 경우 O(2n)의 복잡도를 가질 수 있다)

 

정렬되었을 때

 

삽입 : 아이템을 넣기 위해서는 해당 배열에 있는 아이템의 우선순위를 비교하여 데이터를 넣어야 한다. 이 과정에서 기존에 해당자리에 있는 아이템들을 뒤쪽으로 밀어야 하기 때문에 O(n)의 시간 복잡도를 가진다. 

배출 : 해당 배열은 우선순위가 높은 아이템을 해당 배열의 끝에 보관하기 때문에 시간복잡도는 O(1)이 된다. 

 

연결리스트로 우선순위큐를 구현할 때 

링크드리스트로 만든 우선순위 큐는 배열로 만든 큐와 반대로 되어있다. 정리되어있는 연결리스트는 배출 시 o(1)의 시간복잡도를 가지고 있고 삽입 시 해당 연결리스트를 모두 확인해야 하기 때문에 O(n)의 시간복잡도를 가진다. 

 

정리되어 있지 않은 연결리스트는 배출시 O(n)의 시간복잡도를 가지고 있고 삽입시 O(1)의 시간복잡도를 가지고 있다 .