우선순위 큐/Priority Queue

algorithm/common

우선순위 큐/Priority Queue

아르르르를를르 2022. 2. 27. 14:49

queue인 것에서 알 수 있듯이 push, top, pop 메소드가 있으며,

일반 queue에서는 FIFO 구조로 저장하는 선형 자료구조인데 반해,

prioirty queue의 비선형 자료구조로 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 우선순위는 MAX, MIN으로 지정하기 나름이다.

구현 방식으로는 배열, 연결 리스트, 힙 등이 있다.

보통 최악의 경우라도 가장 나은 성능을 보이는 heap이라는 자료구조로 구현된다. 원소들을 넣고 정렬할 때 heap sort를 사용한다. heap은 완전 이진 트리 구조인데, BST(Binary Search Tree)와 달리 중복된 값이 허용된다.

Enqueue(삽입)

예시로 15라는 데이터가 들어왔을때 동작 순서이다.

Dequeue(삭제)

20이라는 데이터를 삭제하였을 때 동작 순서이다. 항상 root node를 제거한다. index가 가장 큰 데이터를 root로 올리고 root부터 새로 정렬을 시작한다.

사용

보통 라이브러리로 구현되어 있어 가져다 쓰면 된다.

import java.util.PriorityQueue;

// 우선순위 ascend
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// 우선순위 descend
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

구현

나중에 추가할 예정

티스토리