[C언어] Tree / Heap 힙 구현 - 2편

Heap

우선순위 큐를 구현하기 위한 자료구조, 완전 이진 트리의 형태로 구성

최대값 및 최솟값을 찾아내는 연산을 빠르기 하기 위한 용도로 사용

큐는 여기 글에서 설명이 되어있고, 우선순위 큐는 먼저 들어온 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 형태

 

특징

• 완전이진트리의 형태
• 부모노드와 자식노드 간에만 대소 관계가 성립(형제 사이에는 정해지지 않는다)
• 중복된 값 허용

 

복잡도

 

Max Heap (최대 힙)

• 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
• 루트노드의 값은 최대값

 

Min Heap (최소 힙)

• 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙
• 루트노드의 값은 최솟값

연산

• createHeap() : 히프 생성
• deleteHeap() : 히프 삭제
• insert() : 자료 추가
  
  • 트리의 마지막 자리에 임시 저장
  • 부모 노드와 키 값 비교 및 이동

히프 시각적으로 표현

•  remove() : 자료 제거
  • 루트노드의 삭제
  • 트리 마지막 자리 노드의 임시 이동
  • 자식 노드와 키 값 비교 및 이동 (우선 순위가 높은 자식 노드와 위치 교환)

• find() : 루트값 반환

---

코드 구현

기입할 예정