우선 순위 큐 정의, 구현 방법, 완전 이진 트리

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

 우선순위 큐

우선순위 큐는 '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조'이다.
 우선순위 큐는 데이터를 '우선순위에 따라' 처리하고 싶을 때 사용한다.
  예) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우

 

자료구조	추출데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터 (비교적 공평한 자료구조)
우선순위 큐	우선순위가 높은 데이터

우선순위 큐를 구현하는 방법은 다양함.
 1) 단순히 '리스트를 이용한 구현'
 2) '힙을 이용한 구현'
 

 

데이터의 개수가 N개 일 때, 구현 방식에 따라 시간 복잡도를 비교한 내용은 다음과 같다.

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

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일. (힙 정렬)
  이 경우 시간 복잡도는 O(N logN) 이다.

 

 

 

힙의 특징
 힙은 완전 이진 트리 자료구조의 일종임.
 힙에서는 항상 '루트 노드를 제거함'
 
 최소 힙 
  -루트 노드가 가장 작은 값을 가짐.
  -따라서 값이 작은 데이터가 우선적으로 제거 됨.
 
 최대 힙
  -루트 노드가 가장 큰 값을 가짐.
  -따라서 값이 큰 데이터가 우선적으로 제거 됨.

 

완전 이진 트리

 완전 이진 트리란 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가
 차례대로 삽입되는 트리를 의미함.

 

 최소 힙 구성 함수 : Min-Heapify()
  (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체함.
 

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

 

 원소가 제거될 때
  원소가 제거되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있음.
  -원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 함.
  -이후에 루트 노드에서 하양식으로(더 작은 자식 노드로) Heapify()를 진행함.

 
 

---