[트리] 히프 Heap 6/25

*히프
 1. 특징
  - 루트 노드가 언제나 그 트리의 최대값 혹은 최솟값을 가지는 독특한 구조의 완전 이진 트리
 
 2. 종류
  - 최대 히프 : 최대 트리(각 노드의 키 값이 작은 자식 노드의 키 값보다 크가나 같은 트리)의 속성을 가진 히프
  ex) 

  - 최소 히프 : 최소 트리(각 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 트리)의 속성을 가진 히프
  ex) 

 3. 히프의 삽입/삭제 연산
  - 히프의 삽입/삭제 연산은 연산 뒤에 정렬이 따른다.
  ⓐ 히프의 삽입
   : 히프에 값을 삽입하면, 완전 이진 트리의 특징에 맞는 위치에 값이 삽입되며, 그 뒤에 그 값이 히프로서의 특징을
     가질 수 있는 위치로 정렬/이동을 하게된다.
   ex) 최대 히프에서의 삽입을 예로 들겠다.  

 ⓑ 히프의 삭제
  : 삭제 연산은 루트에서 이루워진다. 루트의 값을 삭제 한뒤, 완전 이진트리로서의 가장 마지막 노드를 루트노드로
    이동을 한후 재정렬/이동을 실시한다.
  ex) 최대 히프를 가지고 예를 들겠다.

 4. 히프의 응용 : 우선순위 큐의 구현
  ⓐ 우선순위 큐란?
   - 노드 반환(Dequeue 작업)시 큐에서 우선순위가 가장 높거나 낮은 노드를 먼저 삭제하는 큐이다.
   - 일반 적인 큐의 성질인 FIFO(First In First Out)의 성질을 가지지 않는다.
    ex)

  ⓑ 우선순위 큐를 히프로 구현시 좋은 이유는...?
   - 우선순위 큐에서의 주 관점은 최대 또는 최소 우선순위 값을 가진 값을 이용하는 것이다.
    > 이는 히프에서 루트 노드가 트리에서의 가장 큰 값이나 작은 값을 가진 다는 것을 이용하면 쉽게 된다.
   - 또한, 복잡도 또한 삽입및 삭제의 복잡도 또한 O(lg2n)으로 효율 적이다.