[자료구조 Java] 비선형 자료구조 ③ 힙, 우선순위 큐

비선형 자료구조란?

: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말하며 일반적으로 트리나 그래프를 의미

3. 우선순위 큐

: 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조

- 데이터들이 우선순위를 가지고 있고, 우선 순위가 높은 데이터가 먼저 나감

- 우선순위 큐는 배열, 연결리스트, 힙으로 구현 가능하며 힙으로 구형하는 것이 가장 효율적

구현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
힙	O(log n)	O(log n)

3-1. 우선순위 큐의 활용

- 시뮬레이션 시스템

- 네트워크 트래픽 제어

4. 힙 (Heap)

: 완전 이진 트리 기반의 자료구조로, 최소힙과 최대힙 두 가지가 있으며 해당 힙에 따라 특정한 특징을 가진 트리

4-1. 힙의 종류

구분	최대힙	최소힙
설명	부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같음	부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같음

4-2. 힙의 삽입

- 힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어 삽입
- 새로운 노드를 부모 노드들과 교환해가며 힙의 성질을 만족시킬 수 있도록 한다

4-3. 힙의 삭제

- 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제(최대힙에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것)
- 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
- 계속해서 스왑하며 힙을 재구성