[Algorithm] 우선순위 큐 - 배열

우선순위 큐를 배열로 구현해보기

• 우선순위 큐란 간단하게 말해서 일반적인 큐와 달리 pop을 할 때 임의로 '우선순위'를 정해놓고, FIFO(First In First Out)를 따르지않고, 정해진 우선순위대로 pop이 되는 큐를 말한다.
• 그래서 push를 할 때는 js에서 push() 메서드를 해주는 것처럼 단순히 push를 해주면 된다.
• 하지만, 이를 pop할 때는 우선순위에 따라 pop을 하거나 top()메서드에서 가장 우선순위가 높은 요소를 console.log로 찍어줘야할 것이기 때문에 나는 배열으로 우선순위 큐를 만들되 그 배열에 요소를 넣을 때 [우선순위, 요소] 를 하나의 요소로 집어넣을 생각이다.
• 이렇게 해서 만약 pop을 하면, 각 요소의 인덱스 0에 있는 우선순위를 비교해서 가장 우선순위가 높은 것을 찾아내고, 그 요소를 지우는 작업을 해줄 예정이다.

• 위에 코드는 위에서 말한 pop메서드를 구현한 코드이다. queue라는 배열의 요소를 하나하나 탐색하며, 그 요소의 인덱스 0에 있는 우선순위 중에 가장 큰 순위를 찾아내고, 그 다음 for문에서 이전 for문에서 찾은 우선순위에 해당하는 요소를 삭제해준다. 이렇게 하면 O(n) + O(n) = 결국 O(n)의 시간복잡도를 가지게 된다.

• 아래 코드는 위의 pop을 바탕으로 작성한 top() 메서드이다(우선순위가 가장 높은 요소를 출력하는 메서드).
  

• 마지막으로 가장 간단한 push()메서드이다.
  

• 이렇게 구현한 우선순위 큐는 시간복잡도 측면에서 너무나도 비효율적이다. why? 만약 십만개의 요소를 pop한다고 생각해보자. 물론 push를 할 때는 O(십만)이므로 그렇게 부담스럽지 않은 복잡도를 가지지만, pop을 십만개하면 얘기가 달라진다. 한개를 pop할 때 O(N)의 시간복잡도를 갖는 pop메서드를 십만번을 사용한다면 결국 O(N**2)이 돼서 너무나도 비효율적인 시간복잡도를 가지게 된다.

• 그렇다면 좀더 효율적인 우선순위 큐를 구현할 수는 없을까??

해결책 : 힙(heap)을 이용한 우선순위 큐 (다음 포스팅에서..)