노트

우선순위 큐

Priority Queue

CS#algorithm · 연결된 개념 4개

쉽게 말하면

우선순위 큐는 응급실 대기실 같아요. 먼저 온 순서가 아니라 가장 위급한 환자부터 진료하니까, 늦게 들어온 일이라도 급하면 먼저 꺼내 처리할 수 있어요.

비유가 깨지는 곳 응급실 규칙은 순서만 말해 줘요. 가장 급한 것을 빨리 꺼내려면 구조가 필요해서, 보통 이진 힙으로 넣기·꺼내기를 O(log n)에 해요. 같은 우선순위끼리 순서는 보장하지 않아요.

원소마다 우선순위가 있고, 들어온 순서와 상관없이 우선순위가 가장 높은 것부터 꺼내는 추상 자료형(Abstract Data Type, ADT). 같은 우선순위끼리의 순서는 보장하지 않는다. 응급실 대기 순서가 좋은 비유다.

구현 방법

  • 정렬 안 된 배열: 넣기는 O(1)이지만 꺼낼 때마다 전체를 훑어 O(n)
  • 이진 힙: 넣기·꺼내기 모두 O(log n). 표준 구현이다. 보통 최소 힙을 쓰고 "숫자가 작을수록 우선순위가 높다"로 정한다
type Item<T> = { value: T; priority: number }
// 최소 힙: 부모의 priority가 자식보다 작거나 같다
// enqueue: 끝에 넣고 bubble up / dequeue: 루트를 꺼내고 마지막을 루트로 올려 sink down

어디에 쓰나

  • 다익스트라 최단 경로: 아직 확정되지 않은 노드 중 거리가 가장 짧은 것을 꺼낸다
  • 작업 스케줄러: 운영체제 프로세스 스케줄링, React가 업데이트에 우선순위(레인, Lane)를 매겨 급한 입력부터 처리하는 것도 같은 생각이다(동시성 렌더링)
  • 상위 k개 구하기, 이벤트 시뮬레이션, 허프만 코딩(Huffman Coding)

언어마다 내장 여부가 다르다. 파이썬은 heapq, 자바는 PriorityQueue가 있지만 JavaScript에는 내장이 없어 직접 만들거나 라이브러리를 쓴다. 도착 순서대로 꺼내는 보통의 큐와 비교해 보면 차이가 분명하다.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 정렬 알고리즘

    컬렉션의 원소를 어떤 순서(크기, 사전순, 날짜…)로 다시 배치하는 알고리즘. 같은 일을 하는 방법이 여럿이고 각자 강점이 달라, 트레이드오프를 익히기 좋은 주제다.

  • 기본형 집착

    전화번호·금액·우선순위 같은 도메인 개념을 끝까지 문자열이나 숫자로만 다루는 냄새. 같은 검증과 포맷 코드가 여기저기 반복되고, 문자열로 모든 걸 표현하는 "stringly typed" 코드가 된다.

  • 연결 리스트

    각 노드가 값과 다음 노드를 가리키는 포인터를 가지고 사슬처럼 이어진 자료구조. 리스트는 맨 앞(Head)과 맨 뒤(Tail), 길이 정도만 기억한다. 배열과 달리 인덱스가 없다.

  • 해시 테이블

    키를 해시 함수(Hash Function)로 배열 인덱스로 바꿔 값을 저장하는 자료구조. 조회·추가·삭제가 평균 O(1)이다. JavaScript의 객체와 Map·Set, 파이썬의 dict·set(python-collections), 자바의 HashMap이 모두 해시 테이블이다.

  • 트리 순회

    트리의 모든 노드를 한 번씩 방문하는 방법. 같은 층을 먼저 훑는 너비 우선(Breadth-First)과, 한 가지를 끝까지 내려가는 깊이 우선(Depth-First)이 있고, 깊이 우선은 노드를 언제 방문하느냐에 따라 셋으로 나뉜다.

보기 옵션