힙 트리

우선순위 큐를 위해 만들어진 자료구조

최소 값이나 최대 값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 한 자료구조

• 우선순위 큐 : 우선순위 개념을 큐에 도입한 자료구조.
  • 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나간다.
• 반 정렬 상태
• 완전 이진 트리의 일종
• 중복 값을 허용

종류

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

구현

• 힙 구현의 표준은 배열이다.
• 부모와 자식 인덱스는 항상 정해져 있다.
  

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

관련 알고리즘

힙 생성(정렬)