Kotlin Priority Queue(우선순위 큐)

우선순위 큐는 정해진 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조이다.

 

구현

단순 array / list 하여 구현

- 삽입 O(1)

- 삭제 O(N)

 

힙을 사용하여 구현

- 삽입 O(logN)

- 삭제 O(logN)

 * 모든 데이터를 힙으로 구현된 우선순위 큐에 담았다가 꺼내면 정렬된다(힙 정렬 - O(NlogN))

 

 

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

 

A가 B의 부모노드(parent node) 이면, A의 키값과 B의 키값 사이에는 대소관계가 성립한다.

 

* 완전 이진 트리

- 높이가 h 일 때 레벨 h-1까지는 Full Binary Tree이고, 레벨 h에서는 왼쪽부터 노드가 순서대로 채워진 이진트리

 

최소 힙(min heap)

- root node 가 가장 작다

- 부모 노드는 자식 노드 보다 작다

 

최대 힙(max heap)

- root node 가 가장 크가

- 부모 노드는 자식 노드 보다 크다

 

heapify

- 주어진 힙 조건에 따라 힙(Heap)을 생성하는 과정이다.

 

heap Insert() O(logN)

1. 새로운 데이터가 들어오면 새로운 노드를 힙의 마지막 노드 다음에 삽입

2. 새로운 노드를 부모 노드와 비교하고 조건에 따라 교환하여 힙을 생성한다.

 

heap delete() O(logN)

1. 루트 노드를 삭제

2. 삭제된 루트 노드에 힙의 마지막 노드를 교환한다.

3. 삽입된 노드를 자식 노드와 비교하고 조건에 따라 교환하여 힙을 생성한다.

 

Kotlin 

 

java의 Priority Queue를 랩핑 하여 사용한다.