힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조로서 다음과 같은 힙 속성을 만족한다. A가 B의 부모노드 이면, A의 키값과 B의 키값 사이에는 대소관계가 성립한다. 위키백과

• 우선순위 큐를 위해 만들어진 자료구조다
• 우선순위 큐:
  • 큐에 우선순위를 도입한 자료구조. 우선순위가 높은 데이터부터 삭제된다. (먼저 나간다)
  • 배열, 연결리스트, 힙으로 구현 가능. 힙이 가장 효율적
• 최댓값/최솟값을 빠르게 찾아내도록 만들어졌다.
• 힙 트리는 중복 값을 허용한다

종류

• 최대 힙(max heap)

  부모노드 키 값 ≥ 자식노드 키값

• 최소 힙(min heap)

  부모노드 키 값 ≤ 자식노드 키값

구현

• 완전이진트리이기 때문에 각 노드에 인덱스를 부여해 배열로 구현이 가능하다.
• 편의를 위해 0인덱스는 사용하지 않는다.
• 특정 위치의 노드 인덱스는 새로운 노드가 추가되더라도 변하지 않는다. ex) 루트노드의 오른쪽 노드 번호는 항상 3

왼쪽 자식의 인덱스 = 부모 인덱스 * 2

오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1

부모의 인덱스 = 자식의 인덱스 / 2 (몫)

heap의 삽입(Upheap 연산)

1. 요소를 가장 하위 레벨의 최대한 왼쪽으로 삽입 ( 배열에선 가장 마지막)
2. 부모값과 비교해 더 작은 경우 위치 변경 (위치 변경이 없을 때 까지 반복)