정렬 (10) - 힙 정렬 (Heap Sort) (1)

1. Priority Queue (우선순위 큐)

• 새로운 데이터를 넣고, 가장 우선순위 높은 데이터를 출력하는 추상적인 자료구조

• 여러가지 구조로 우선순위 큐를 구현할 수 있음. (우선순위 큐는 추상적인 자료구조)

• 구조 1) Stack : 가장 나중에 들어간 데이터 출력 (LIFO)

• 구조 2) Queue : 가장 먼저 들어간 데이터 출력 (FIFO) 

• 구조 3) Heap : 가장 큰 데이터 출력 (Biggest Out)

 

2. Heap (힙)

• 키 값의 크기가 우선순위가 되며, 완전 이진 트리로 구현됨.

• 완전 이진 트리 : 원소가 왼쪽 자식노드로 차곡차곡 쌓여서 빈칸이 없는 이진트리

• 최대 힙 : 부모노드가 반드시 두 자식노드보다 커야하는 트리 (가장 큰 값이 Root)

• 최소 힙 : 부모노드가 반드시 두 자식노드보다 작아야하는 트리 (가장 작은 값이 Root)

 

[그림] 힙 (Heap) 구조