힙

• 힙은 우선순위 큐를 위해 만들어진 자료구조이다.
• 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
• 우선순위큐 사용 : 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산

힙의 특징

• 완전 이진 트리 형태이다.
• 중복값을 허용한다.
• 반 정렬 상태이다.
  • 최소 heap: 부모 < 자식
  • 최대 heap: 부모 > 자식
  • 형제 노드간 정렬은 X
• 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조이다.

최소 힙 - 삽입

1. 트리의 가장 끝 위치에 데이터 삽입

2. 부모 노드와 키 비교한 후 작을 경우 부모 자리와 교체를 반복한다.

   

최소 힙 - 삭제

1. 최상위 노드 반환 및 삭제

2. 가장 마지막 위치의 노드를 최상위 노드로 위치 시킴

3. 자식 노드 중 작은 값과 비교 후 부모노드가 더 크면 자리 교체를 반복

   

시간 복잡도

삽입	삭제
O(log n)	O(log n)

두 연산 모두 최악의 경우 heap의 높이만큼의 시간복잡도가 든다.
힙은 완전이진 트리이므로 높이는 log n을 넘지 않는다.