힙(heap)

힙(heap)

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

• 최대 힙(max heap)

  • 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 > 자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 큰 노드

• 최소 힙(min heap)

  • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 < 자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 작은 노드

힙 예시

힙 연산 - 삽입

최대힙에서 루트노드보다 큰 값을 삽입하였을 때 자리를 바꿔가는 형식으로 삽입된다.

힙 연산 - 삭제

• 힙에서는 루트 노드의 원소만을 삭제 가능
• 루트 노드의 원소를 삭제하여 반환
• 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.

힙의 활용

힙의 활용1 - 우선순위 큐(Priority Queue)

• 우선순위 큐를 구현하는 가장 효율적인 방법이 힙을 사용하는 것
  • 노드 하나의 추가/삭제의 시간 복잡도가 O(logN)이고 최대값/최소값을 O(1)에 구할 수 있다.
  • 완전 정렬보다 관리 비용이 적다.
• 배열을 통해 트리 형태를 쉽게 구현 가능
  • 부모나 자식 노드를 O(1)연산으로 쉽게 탐색 가능
  • n위치에 있는 노드의 자식은 2n과 2n+1위치에 존재
  • 완전 이진 트리의 특성에 의해 추가/삭제의 위치는 자료의 시작과 끝 인덱스로 쉽게 판단할 수 있다.

우선순위 큐의 특성

• 우선순위를 가진 항목들을 저장하는 큐
• FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나간다.

힙의 활용2

• 힙 정렬은 힙 자료구조를 이용해서 이진 트리와 유사한 방법으로 수행된다.
• 정렬을 위한 2단계

1. 하나의 값을 힙에 삽입(반복)
2. 힙에서 순차적(오름차순)으로 값을 하나씩 제거

• 힙 정렬의 시간 복잡도
  • N개의 노드 삽입 연산 + N개의 노드 삭제 연산
  • 노드 하나의 삽입과 삭제 연산은 각각 O(logN)이다.
  • 따라서, 전체 정렬은 O(NlogN)이다.