자료구조 - 우선순위큐(힙)

- priority queue

- 배열, 리스트 사용하여 구현시 최악의경우로 삽입, 삭제에 O(n)

- 힙 (heap)
 : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료 구조, 더미
 : 일종의 반정렬 상태를 유지
 : 삽입과 삭제에 
 : 최대 힙: 부모 노드 >= 자식 노드, 최소 힙: 부모 노드 <= 자식노드
 : 삽입
  ① 힙의 끝에 새로운 노드 삽입
  ② 삽입된 노드와 그 부모 노드의 키 값을 비교하여 삽입된 노드의 키 값이 부모 노드의 키 값보다 크면 두 노드의 위치를 바꾼다.
  ③ 삽입된 노드의 키 값이 자신의 부모 노드 키 값보다 작아질 때까지 단계 ② 반복
 : 삭제
  ① 루트 노드 삭제하고, 마지막 노드를 루트에 삽입
  ② 자식 노드랑 스왑해나가는데, 이때 왼쪽, 오른쪽 자식노드 중 더 큰 쪽이랑 교환
  ③ 자식 노드들이 작을때까지 ② 반복

 : 허프만 코드에 이용 가능 (최소힙 사용)
   알파뱃의 빈도수를 이용하여 저장하고, 디코딩은 코드 테이블을 이용하여 수행할 수 있다.

- 완전(complete)라는 의미?
  : 노드들이 힙 조건을 만족한다. O
  : 마지막 행만 제외하고 모든 행이 노드로 채워져 있다. X