heap1 4. Priority Queue & Heap Priority Queue란? Queue의 경우 먼저 들어간 데이터가 먼저 나오게 된다. Priority Queue는 이와 다르게 들어간 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나오게 된다. 그렇다면 Priority Queue를 어떻게 구현해야 할까? 첫번째, 배열로 구현하여 삽입 시마다 우선순위에 맞게 정렬한다. 이 방법은 항상 정렬된 형태를 유지하기 때문에 데이터를 꺼낼 때 용이하지만, 삽입 시 O(n)의 시간이 필요하다. 두번째, 리스트로 구현하여 데이터를 불러올 때 우선순위가 높은 데이터를 찾는다. 이 방법은 삽입 시 상수 시간이 걸려 용이하지만, 데이터를 꺼낼 때마다 O(n)의 시간이 필요하다. 이처럼 배열과 리스트로 Priority Queue를 구현하면 이와 같이 데이터 삽입이나 요청.. 2020. 5. 22. 이전 1 다음
