JS 트리 & 우선순위 큐

트리: 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조

루트 노드: 부모가 없는 최상위 노드

단말 노드: 자식이 없는 노드

 

트리는 부모와 자식 관계가 성립한다.

깊이: 루트 노드에서의 길이 (*길이: 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수)

트리의 높이: 루트 노드에서 가장 깊은 노드까지의 길이

 

이진 트리

: 최대 2개의 자식을 가질 수 있는 트리

 

우선순위 큐: 우선 순위에 따라서 데이터를 추출하는 자료구조

컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용

일반적으로 힙을 이용하여 구현

 

자료구조	추출되는 데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

우선순위 큐 구현 방법

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트 자료형	O(1)	O(N)
힙	O(logN)	O(logN)

 

일반적인 형태의 큐는 선형구조

반면 우선순위 큐는 이진트리 구조(비선형 구조)

 

포화 이진 트리

: 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리.

 

완전 이진 트리

: 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리.

 

높이 균형 트리

: 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1이상 차이나지 않는 트리.

 

힙

: 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조.

최대힙: 값이 큰 원소부터 추출 / 최소힙: 값이 작은 원소부터 추출.

원소의 삽입과 삭제를 위해 각각 O(logN) 수행시간 요구

만약 단순한 N개의 데이터를 힙에 넣었다가 꺼내는 작업(=정렬과 동일)은 O(N*logN)

 

최대힙: 부모 노드가 자식 노드보다 값이 큰 완전 이진트리

 

힙은 완전 이진트리 자료구조를 따른다.

힙에서는 우선순위가 높은 노드가 루트에 위치한다.

1. 최대 힙

: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다.

루트 노드가 가장 크며, 값이 큰 데이터가 우선순위를 가진다.

2. 최소 힙

: 부모 노드의 키 값이 자식노드의 키 값보다 항상 작다.

루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다.

 

* 최소 힙 구성 함수: Heapify

힙에 새로운 원소가 삽입될 때

(상향식) 부모로 거슬러 올라가며, 부모보다 자신이 더 작은 경우 위치를 교체

새로운 원소가 삽입되었을 때 O(log N)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

 

힙에 원소가 삭제될 때

원소가 제거되었을 때 O(log N)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.

이후에 루트 노드에서 하향식으로(더 작은 자식 노드로) heapify() 진행

 

JS는 기본적으로 우선순위 큐 라이브러리 제공x

최단경로 알고리즘 등에서 힙이 필요하면 별도의 라이브러리 사용=>PriorityQueue