트리 : 우선순위 큐

완전 이진트리 형태의 자료구조

일차원 배열로 구현

배열로 구현하였기 때문에 부모 또는 자식 노드를 찾아가는 연산을 구현하기도 간편하다.

• 왼쪽 자식노드 index = (부모 노드 index) * 2
• 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1

• 부모 노드 index = (자식노드 index) / 2

출처 : https://suyeon96.tistory.com/31

 

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

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

 

힙(Heap) 삽입연산

1. 트리의 가장 마지막 위치에 노드 추가

2. 추가된 노드와 그 부모 노드관계가 힙조건을 만족하는지 확인

3. 만족하지 않을 경우 부모와 자식의 키값 교환

4. 조건이 만족하거나 추가된 노드가 root 노드가 될때까지 2, 3번 과정 반복

 

우선순위 큐(Priority Queue) : 힙(Heap) 구조를 기반으로 하는 자료구조

- 각 데이터에 우선순위를 부여하여 큐에 넣은 데이터를 꺼낼 때 우선순위가 높은 데이터를 먼저 꺼내는 자료구조

- 큐에 데이터를 우선순위를 지정하여 추가

- 큐에서 가장 우선순위가 높은 데이터를 제거하고 반환

- Java의 경우 Min Heap(작은 값의 우선순위가 높음)으로

  C++의 경우 Max Heap(큰 값의 우선순위가 높음)으로 적용