힙(Heap)

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

최대 힙(max heap)

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

최소 힙(min heap)

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

힙 연산 - 삭제

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

힙(Heap)활용

힙의 활용1 - 우선순위큐

우선순위 큐를 구현하는 가장 효율적인 방법이 힙을 사용한는 것이다.

  • 노드 하나의 추가/삭제의 시간 복잡도가 O(logN)이고 최대값/최소값을 O(1)에 구할 수 있다.
  • 완전 정렬보다 관리 비용이 적다.

배열을 통해 트리 형태를 쉽게 구현할 수 있다.

  • 부모나 자식 노드를 O(1)연산으로 쉽게 찾을 수 있다.
  • n위치에 있는 노드의 자식은 2n과 2n+1위치에 존재한다.
  • 완전 이진 트리의 특성에 의해 추가/삭제의 위치는 자료의 시작과 끝 인덱스로 쉽게 판단할 수 있다.

우선순위 큐의 특성

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

java.util.PriorityQueue

  • Heap 자료구조
  • 최대 heap
    • 가장 큰 값을 기준으로 먼저 나옴
  • 최소 heap
    • 가장 작은 값을 기준으로 먼저 나옴

java.util.PriorityQueue()

  • 원소들의 natural Ordering에 따라 Heap 유지
  • 따라서 반드시 모든 원소는 Comparable 인터페이스를 구현해야 함

java.util.PriorityQueue(Comparator comparator)

  • 명시된 Comparator의 구현에 따라 원소들의 순서를 유지

힙의 활용2

  • 힙 정렬은 힙 자료구조를 이요해서 이진 트리와 유사한 방법으로 수행된다.
  • 정렬을 위한 2단계
    1. 하나의 값을 힙에 삽입한다(반복).
    2. 힙에서 순차적(오름차순)으로 값을 하나씩 제거한다.
  • 힙의 정렬의 시간 복잡도
    • N개의 노드 삽입 연산 + N개의 노드 삭제 연산
    • 노드 하나의 삽입과 삭제 연산은 각각 O(logN)이다.
    • 따라서 전체 정렬은 O(NlogN)이다.