[자료구조] 힙 (Heap)

Heap

heap

• 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료형으로 우선순위 큐를 위해 만들어진 자료구조
• 사용 : 시뮬레이션 시스템, 작업 스케쥴링, 수치해석 계산
• 완전 이진 트리의 일종으로, 각 노드의 키 값이 그 자식의 키 값보다 작지않거나(최대 힙), 크지않은(최소 힙) 완전 이진 트리이다.
  - 완전 이진 트리는 중복을 허용하지 않지만 힙은 중복 허용
  

최대 힙 (Max Heap)

• 부모 노드의 키 값이 자식 노드의 키 값다 큰 힙

최소 힙 (Min Heap)

• 부모 노드의 키 값이 자식 노드의 키 값다 작은 힙

• 부모 자식의 인덱스 관계
  - 오른쪽 자식 인덱스 = (부모의 인덱스)*2+1

  • 왼쪽 자식 인덱스 = (부모의 인덱스)*2
  • 부모 인덱스 = (자식 인덱스)/2

힙의 삽입

• 힙에 삽입 시, 제일 마지막 노드에 삽입
• 힙의 특징에 맞게 (최소 힙 / 최대 힙) 부모와 자식을 교환
• 시간복잡도 : O(logn)

힙의 삭제

• 힙의 삭제는 항상 루트에서만 해야 함
• 루트에서 삭제를 한 뒤 다음 루트가 될 노드를 선택 (선택 방식은 다음과 같다.)
  • 루트 노드를 삭제
  • 트리의 레벨 중 가장 마지막 노드를 루트로 옮김
  • 힙의 종류에 맞게(최대힙, 최소힙) 루트로 옮겨진 노드와 자식 노드를 비교하면서 힙 조건을 검사
  • 만약 힙의 조건에 만족하지 않으면 교환
  • 힙 조건에 만족할 때까지 반복
• 시간복잡도 : O(logn)