[자료구조] - 힙

1. 우선순위 큐

• 우선순위의 개념을 큐에 도입한 자료구조
• 우선순위가 높은 데이터가 먼저 나감

2. 우선순위 큐 사용

• 시뮬레이션 시스템, 작업 스케쥴링, 수치해석 계산

우선순위 큐는 배열, 연결리스트, 힙으로 구현(힙이 가장 효율적)

힙 -> 삽입 : O(logn), 삭제 : O(logn)

3. 힙

• 우선순위 큐를 위해 만들어진 자료구조.
• 완전 이진트리의 일종
• 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
• 반 정렬 상태
• 힙 트리는 중복 값 허용 (이진트리 - X)

4. 힙 종류

• 최대 힙(max heap)
  부모 노드의 키 값이 자식 노드의 키 값 보다 크거나 같은 완전 이진트리
• 최소 힙(min heap)
  부모 노드의 키 값이 자식 노드의 키 값 보다 작거나 같은 완전 이진트리

5. 구현

• 힙을 저장하는 표준적인 자료구조는 배열
• 구현을 쉽게하기 위해 배열의 첫번째 인덱스 0 사용 X

6. 부모 - 자식

• 왼쪽 자식 index = (부모 index) * 2
• 오른쪽 자식 index = (부모 index) * 2 + 1
• 부모 index = (자식 index) / 2

7. 힙의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입
2. 새로운 노드를 부모 노드들과 교환

8. 힙의 삭제

1. 최대 힙에서 최대값은 루트 노드 이므로 루트 노드가 삭제됨
   (최대 힙에서 삭제 연산은 최대값 요소를 삭제 하는것)
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
3. 힙의 재구성