[Kotlin] PriorityQueue란 무엇인가? Priority Queue의 삽입, 삭제, 탐색을 위한 시간 복잡도 알아보기

2023. 5. 31. 21:19· Kotlin/Kotlin 자료구조
목차
  1. PriorityQueue란?
  2. PriorityQueue의 시간 복잡도
  3. 원소를 삽입하기 위한 시간 복잡도
  4. 원소를 우선 순위가 가장 높은 원소를 가져오고 삭제하기 위한 시간 복잡도
  5. 특정 원소를 탐색을 위한 시간 복잡도
  6. 특정 원소 삭제를 위한 시간 복잡도
  7.  
반응형

PriorityQueue란?

PriorityQueue는 원소들을 우선순위에 따라 저장하고 관리하는 자료구조이다. 각각의 원소는 우선순위의 순서대로 저장된다.

 

PriorityQueue는 일반적으로 min-heap 이나 max-heap을 사용해 구현된다. Heap은 트리 형태의 우선순위대로 순서가 나타내지는 자료 구조로. min-heap 방식으로 구현되면 우선순위가 낮은 요소가 맨 앞에 오고, 우선순위가 높은 요소가 맨 뒤에 오게 되며, max-heap 방식을 사용해 구현되면, 우선순위가 높은 요소가 맨 앞으로 오고 우선순위가 낮은 요소가 맨 뒤에 위치한다. 

 

Kotlin과 Java의 PriorityQueue는 min-heap 방식으로 구현되어 우선순위가 낮은 요소가 가장 앞쪽에 온다. 예를 들어 아래와 같이 12, 14, 13을 순서대로 입력할 경우 우선순위가 낮은 12가 맨 앞으로 오고 우선순위가 높은 14가 맨 뒤로 간다.

val priorityQueue = PriorityQueue<Int>()
priorityQueue.offer(12) // [12]
priorityQueue.offer(14) // [12, 14]
priorityQueue.offer(13) // [12, 13, 14]

 

PriorityQueue의 시간 복잡도

PriorityQueue는 Queue이기 때문에 얼핏 보기에는 우선순위에 따라 Linear하게 구성되는 것처럼 보이지만, 내부적으로는 데이터를 저장하기 위해 우선순위에 따라 Tree 자료 구조를 가진다. 

 

예를 들어 11, 12, 13, 14, 15를 순서대로 PriorityQueue에 넣으면 아래와 같은 형태가 된다.

val priorityQueue = PriorityQueue<Int>()
priorityQueue.offer(11) // [11]
priorityQueue.offer(12) // [11, 12]
priorityQueue.offer(13) // [11, 12, 13]
priorityQueue.offer(14) // [11, 12, 13, 14]
priorityQueue.offer(15) // [11, 12, 13, 14, 15]

그림1. PriorityQueue의 내부

 

 

원소를 삽입하기 위한 시간 복잡도

Heap 구조는 완전 이진트리로 구성되며, 부모 노드의 우선순위는 자식 노드의 우선순위보다 높은 특성을 가진다. 원소를 추가할 때는 새로운 원소를 우선순위 큐의 가장 마지막에 추가한 후 우선 순위에 따라 재배치하는 과정을 거친다. 이 때문에 삽입을 위한 시간 복잡도는 O(logN)이 된다. 

 

원소를 우선 순위가 가장 높은 원소를 가져오고 삭제하기 위한 시간 복잡도

원소를 Queue에서 빼기 위한 시간 복잡도는 맨 앞의 원소를 가져오면 되기 때문에 O(1)이 된다.

 

특정 원소를 탐색을 위한 시간 복잡도

Priority Queue에서 특정 원소를 찾기 위해서는 전체 노드를 우선순위에 따라 반복적으로 확인해야 한다. 이 때문에, O(N)의 시간 복잡도를 가진다.

 

Heap에서 원소를 추가할 때는 바로 위의 부모 노드와만 비교해서 위로 옮길지 말지가 결정되기 때문에 Tree의 Depth에 해당하는 시간 복잡도인 O(logN)을 가지지만, 원소 탐색 시에는 Tree의 Depth가 크기를 나누는데 영향이 없기 때문에 모든 노드를 탐색해야 하기 때문이다.

 

예를 들어 아래와 같은 Min-Heap 구조에서 위에서 맨 왼쪽 3번째에 있는 11은 위에서 맨 오른쪽 2번째에 있는 12보다 작은 것을 확인할 수 있다.

그림2. PriorityQueue 예시

 

특정 원소 삭제를 위한 시간 복잡도

특정 원소를 탐색하기 위한 시간 복잡도는 O(N)이고, 특정 원소 삭제를 위해서는 우선적으로 탐색 수행되어야 하므로 O(n)이 된다.

 

 

 

반응형
저작자표시 비영리 변경금지
  1. PriorityQueue란?
  2. PriorityQueue의 시간 복잡도
  3. 원소를 삽입하기 위한 시간 복잡도
  4. 원소를 우선 순위가 가장 높은 원소를 가져오고 삭제하기 위한 시간 복잡도
  5. 특정 원소를 탐색을 위한 시간 복잡도
  6. 특정 원소 삭제를 위한 시간 복잡도
  7.  


 

Kotlin, Android, Spring 사용자 오픈 카톡

오셔서 궁금한 점을 질문해보세요!
비밀번호 : kotlin22

open.kakao.com

'Kotlin/Kotlin 자료구조' 카테고리의 다른 글
  • [Kotlin] Kotlin PriorityQueue 클래스 사용해 우선순위큐 사용하기
  • [Kotlin] Binary Search Tree Kotlin으로 구현해보기 : insert, search
  • [Kotlin] Binary Search Tree란 무엇인가? Binary Search Tree의 한계와 시간 복잡도 알아보기
  • [Kotlin] Stack 다루는 방법 한 번에 정리하기 : Kotlin의 Stack의 한계와 ArrayDeque를 사용한 해결 방안
Dev.Cho
Dev.Cho
'조세영의 Kotlin World'는 Kotlin를 전문적으로 다루는 개인 기술 블로그입니다. Kotlin 세계에 대한 양질의 자료를 제공하며 Kotlin, Android, Spring, CI, CD 분야에 대해 다룹니다.
Dev.Cho
조세영의 Kotlin World
Dev.Cho
전체
오늘
어제

블로그 메뉴

  • LinkedIn
  • GitHub
  • 분류 전체보기 (491)
    • Kotlin (104)
      • Class and Interface (19)
      • Variable and Function (8)
      • Modifier (5)
      • Collection (14)
      • Time (8)
      • 동시성 제어 (7)
      • Reactive Programming (2)
      • Paradigm (2)
      • Kotlin 자료구조 (15)
      • Design Patterns (11)
      • Algorithm (3)
      • Exception (1)
      • 기타 (9)
      • Update History (0)
    • Coroutines (32)
      • Coroutine Basics (18)
      • Flow (9)
      • CoroutineScope (3)
      • Debugging (2)
    • Testing Codes (28)
      • Test 기본 (3)
      • JUnit5 (9)
      • MockK (6)
      • Testing Coroutines (1)
      • Testing Android (8)
      • Test 기타 (1)
    • Spring (50)
      • Dependency Injection (18)
      • Settings (5)
      • REST API (0)
      • DevTools (1)
      • MVC (18)
      • Error (2)
      • MongoDB (2)
      • Database (4)
    • Android (39)
      • Architecture (2)
      • Component (5)
      • Manifest (1)
      • Lifecycle (2)
      • Dependency Injection (17)
      • Resource (1)
      • Storage (1)
      • Security and Optimization (1)
      • WebView (2)
      • Error (6)
    • Android Jetpack Compose (33)
      • Compose (6)
      • Compose Modifier (13)
      • Compose Resource (4)
      • Compose State (4)
      • Compose Side Effect (6)
    • Android Jetpack Compose UI (48)
      • Compose Layout (14)
      • Compose Text (10)
      • Compose Button (5)
      • Compose Dialog (2)
      • Compose TextField (0)
      • Compose UIs (4)
      • Compose Animation (1)
      • Compose Canvas (12)
    • Android Jetpack (10)
      • Datastore (5)
      • ViewModel (4)
      • LiveData (1)
      • Paging (0)
    • KMP (5)
    • Programming (4)
    • Machine (9)
      • JVM (7)
      • Linux (2)
    • CI, CD (74)
      • Gradle (12)
      • Groovy Gradle (5)
      • Git (25)
      • Git Remote (5)
      • GitHub (5)
      • GitHub Actions (21)
    • Network (33)
      • GraphQL (12)
      • HTTP (11)
      • Basic (9)
    • 오픈소스 (3)
    • Database (3)
      • MongoDB (3)
    • IDE (6)
      • Android Studio (2)
      • Intellij (4)
    • Firebase (1)
    • Javascript (9)

공지사항

  • 코틀린 코루틴 완전 정복 강의 in 인프런 오픈
  • 코틀린 코루틴의 정석 책 출간
  • Kotlin Coroutines 공식 기술 문서 한국어 번⋯
  • GitHub에서 조세영의 Kotlin World를 Foll⋯
  • 문의&제안

인기 글

태그

  • 의존성 주입
  • 유닛 테스팅
  • Android Compose
  • GIT
  • HTTP
  • 안드로이드
  • gradle
  • dagger2
  • 스프링
  • Jetpack Compose
  • Coroutine
  • java
  • Kotlin
  • GraphQL
  • Spring
  • kotlin spring
  • flow
  • junit
  • 코루틴
  • github actions
  • 코틀린
  • Spring boot
  • compose
  • Class
  • junit5
  • github
  • Dependency Injection
  • Unit Testing
  • junit4
  • Android

최근 글

반응형
hELLO · Designed By 정상우.v4.3.0
Dev.Cho
[Kotlin] PriorityQueue란 무엇인가? Priority Queue의 삽입, 삭제, 탐색을 위한 시간 복잡도 알아보기
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.