우선순위 큐

• 우선순위 속성을 갖는 데이터의 삽입과 제거 연산을 지원하는 ADT

Heap

• 힙은 힙 순서 속성을 만족하는 완전이진 트리

힙 순서 속성

• 트리내의 모든 노드가 부모 노드보다 커야(또는 작아야)한다. (MinHeap, MaxHeap에 따라 다름)
• 힙은 이진이 가능하지 않다!! 힙 내에서 어떤 노드를 찾으려면 모든 노드를 순회해야한다.
• 힙에서 가장 작은 (또는 가장 큰)데이터를 갖는 노드는 뿌리노드

힙의 연산

• 연산은 두가지 뿐
  1. 새 노드 삽입

  2. 최솟값 삭제(뿌리 노드를 없앰)

• 삽입
  1. 새로삽입한 노드가 힙 순서 속성을 만족할 때까지 삽입된 노드를 부모노드와 계속해서 교환

• 최솟값 삭제
  1. 뿌리노드 삭제

  2. 힙 최고깊이 가장 우측노드를 뿌리노드 자리로 옮김
  3. 힙 순서 속성을 만족할때까지 자식과 교체

힙의 구현

• 힙은 배열로 구현
• 인덱스 정보로 힙의 각 노드 위치나 부모 자식 관계등을 단번에 알아낼 수 있다.
• K 번째 인덱스에 위치한 노드의 양쪽 자식 인덱스
  왼쪽 : 2K+1
  오른쪽 2K+2
• K번째 인덱스 노드의 부모 인덱스
  (K-1)/2 의 몫
  

---

힙으로 구현하는 우선순위 큐

• 힙은 최솟값(혹은 최댓값)을 즉시(O(1)) 얻어낼 수 있다는 점에서 우선순위 큐를 구현하는데 적격

※ realloc 함수의 사용법
https://dsnight.tistory.com/51