본문으로 건너뛰기

이진 힙

이진검색트리와 유사하지만 다른 규칙이 존재한다.

  • 최대이진힙(MaxBinaryHeap)에서는, 부모노드가 자식노드보다 항상 크다.
  • 최소이진힙(MinBinaryHeap)에서는, 부모노드가 자식노드보다 항상 작다.
  • 각 노드의 자식은 왼쪽부터 채워지며 가능한 모두 채워야 한다.

사용처​

  • 자료구조에서 흔히 사용되는 우선순위 큐를 구현하는데 사용한다.
  • 그래프 순회 알고리즘에서도 꽤 사용된다.

표현​

배열로 표현할 수 있다.

  • 어느 n번째 인덱스 노드의 자식노드 중 왼쪽은 2n + 1 인덱스에, 오른쪽은 2n + 2에 존재한다.
  • 어느 n번째 인덱스 노드의 부모노드는 (n-1)/2에 존재한다. (소수점 버림)

최대이진힙에 추가하기​

  1. 배열의 맨 끝에 추가한다.
  2. 부모와 비교하며 자신이 더 작을 때까지 끌어올린다.

최댓값 추출하기​

  1. 배열의 첫 값과 마지막 값을 교환하고 배열의 마지막 요소를 뽑아 반환 값으로 한다.
  2. 새로운 루트 노드를 자식과 비교하여 본인의 위치까지 끌어내린다.
    1. 왼쪽과 오른쪽 자식 값을 찾는다. (2n + 1, 2n + 2)
    2. 현재 노드보다 큰 자식과 위치를 바꾼다.
    3. 두 자식이 모두 크다면 더 큰 자식쪽으로 위치를 바꾼다.

최소이진힙​

  • 최대이진힙의 추가, 추출의 반대로 진행 (작은게 루트 쪽으로)

이진힙의 시간복잡도​

  • 삽입: O(log N)
  • 삭제: O(log N)
  • 검색: O(N)

우선순위 큐​

각 요소들이 우선순위를 가지는 자료구조이다. 우선순위가 높은 요소가 그렇지 않은 요소보다 먼저 위치한다. 최대이진힙 또는 최소이진힙으로 구현한다.