[자료구조] Priority Queue

김희성의 개발자 면접 cs 강의/ 스터디

 

 

 

Priority Queue

• 비선형 자료구조
• Heap이라는 완전 이진 트리로 구현
• FIFO Queue와 다르게 데이터 삽입 순서와 관계없이 우선순위가 가장 높은(낮은)데이터 먼저 꺼낸다.
• 우선순위 높은 데이터부터 꺼냄 : Max Heap(최대힙) (c++)
• 우선순위 낮은 데이터부터 꺼냄 : Min Heap (최소힙) (java, python)

• 시간복잡도
  • i번째 데이터에 접근(Access) : *NONE
  • 데이터의 삽입 : O(logN)
  • 우선순위가 가장 높은(낮은) 데이터에 접근 : O(1)/삭제:O(logN)
• 데이터가 계속 들어가고 나오는 상태에서 가장 큰 값이나 가장 작은 값을 빠르게 알고싶을 때 사용.  

---

 

import java.util.PriorityQueue;

public class Main {

    private static final int MAX= 200_000;


    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i =0; i<MAX; i++){
            pq.add(i); //O(logN)
        }

        long start= System.currentTimeMillis();

        for(int i=0; i<MAX; i++){
            //System.out.println("pq.poll() = " + pq.poll());
            pq.poll();  //O(logN)
        }
        long end= System.currentTimeMillis();

        System.out.println((end - start)/1000.0 + "");

    }
}

• Max Heap 에서 데이터 추가 과정
  • Add(7)
  • 시간복잡도 O(logN) 
  • 데이터 추가할 때 완전히 정렬되는 것이 아님!!
• Max Heap 에서 우선순위가 가장 높은 데이터의 삭제(접근) 과정
  • Poll() -> 8
  • 시간복잡도 O(logN) 
• add()는 정렬되지않는다. poll()로 꺼내면서 정렬한다.