열혈 자료구조 - 9.1 우선순위 큐의 이해

우선순위 큐

- 우선순위 큐는 들어간 순서와 나가는 순서가 아무런 상관이 없음

- 데이터를 뽑아낼 때 우선순위를 근거로 뽑아냄

- 데이터를 넣고 빼는 연산은 큐와 같이 enque, dequeue이지만 큐와는 꺼내는 방식이 다름

- 우선순위를 판단하고 결정하는 것은 프로그래머가 직접 결정

 

우선 순위 큐를 구현하는 방법

- 배열을 기반으로 구현

    -> 데이터를 넣으면 우선순위에 맞춰 정렬되어 저장

    -> 데이터를 넣으면 앞에서부터 비교하면서 맞는 순위에 삽입이 되고 배열을 한칸 씩 뒤로 이동

- 연결 리스트를 기반으로 구현

    -> 연결 리스트도 마찬가지로 앞에서부터 비교하면서 삽입

    -> 데이터 수가 많을 경우 배열이나 연결 리스트는 성능이 떨어질 수 있음

- 힙(Heap)을 이용하는 방법

 

힙

- 완전 이진 트리

- 힙의 종류

    -> 최대 힙 : 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 함. 루트 노드에 가장 큰 값이 저장됨

    -> 최소 힙 : 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 작거나 같아야 함. 루트 노드에 가장 작은 값이 저장됨

    -> 비교할 때는 부모노드와 자식 노드끼리만 비교해서 만족되면 됨