Heap

힙(heap)이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
• 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
• 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

힙 종류

• 최대 힙(max heap)
  • 부모 노드 값이 자식 노드의 값보다 크거나 같음
  • 루트 값은 저장된 원소 중 가장 큼

• 최소 힙(min heap)
  • 부모 노드 값이 자식 노드의 값보다 작거나 같음
  • 루트 값은 저장된 원소 중 가장 작음

힙 구현

• 배열로 구현
• 인덱스 0 사용하지 않음
• 부모-자식 사이 인덱스 관계
  • 인덱스 i에서 부모인덱스: i/2
  • 인덱스 i에서 왼쪽 인덱스: i * 2
  • 인덱스 i에서 오른쪽 인덱스: ( i * 2 )+1

힙 연산

• 삽입 연산
  1) 마지막 위치에 노드 만들어 삽입 -> 구조적 성질 만족
  2-1) 부모 노드보다 값이 작으면 끝
  2-2) 부모 노드보다 값이 크면 부모노드와 스위치
  3) 2번 과정 최대 루트까지 반복 -> 힙의 성질 만족시키기

  

• 삭제연산
  1) 루트 노드 값 제거
  2) 마지막 노드 값 루트로 옮기고 노드 삭제 -> 구조적 성질 만족
  3-1) 자식 노드보다 값 크면 끝
  3-2) 자식 노드보다 값 작으면 스위치
  4) 3번 과정 최대 리프까지 반복 -> 힙의 성질 만족시키기

  

시간복잡도

• 삽입연산
  • 최악의 경우 교환을 반복하여 리프노드에서 루트노드가 될 수 있음
  • 교환은 O(1)시간에 처리
• 삭제연산
  • 최악의 경우 교환을 반복하여 루트노드에서 리프노드가 될 수 있음
  • 교환은 O(1)시간에 처리

두 연산 모두 최악의 경우 교환 횟수는 힙의 높이(height)가 된다. 힙은 완전 이진 트리이므로 높이가 log_2 n을 넘지 않는다. 따라서 두 연산의 시간복잡도는 O(log n)이다.

 

연산시간복잡도

삽입	O(log n)
삭제	O(log n)

힙 응용 1 - 우선순위 큐

• 큐의 선입선출와 달리 우선순위가 높은 데이터가 먼저 나옴
• 힙을 통해 우선순위 큐 구현

힙 응용 2 - 힙 정렬

• 힙 정렬
  1) 정렬할 데이터 n개 하나씩 힙에 삽입 -> O(n) * O(logn)
  2) 최댓값 차례로 하나씩 삭제하여 보관 -> O(n)
• 시간복잡도: O(nlogn) + O(n) = O(nlogn)

Referece

https://velog.io/@suk13574/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0Java-%ED%9E%99heap

[자료구조/Java] 힙(heap)

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog