[자료구조] Heap(힙)

Heap 이란?

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)이다.
• 일차원 배열과 일대일 대응된다.
• 또한, 우선순위 큐(Priority Queue)를 위해 만들어진 자료구조이다.

  우선순위 큐(Priority Queue)?
  일반적인 큐(Queue)는 FIFO 구조.
  우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것.

우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있기 때문에 이 둘을 묶어서 같이 쓴 것.

Heap의 종류

• 최대 힙(max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모 노드) >= key(자식 노드)
• 최소 힙(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모 노드) <= key(자식 노드)

Heap의 구현

• Heap을 저장하는 표준적인 자료구조는 배열.
• 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않음.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음.
• Heap에서의 부모 노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2
    

Heap의 삽입

1. Heap에 새로운 요소는 Heap의 마지막 노드에 삽입.
2. 새로운 노드를 부모 노드들과 계산 후, 교환하며 Heap의 성질을 만족시킴.

Heap의 삭제

1. Max Heap에서 최댓값은 루트 노드이므로 루트 노드가 삭제됨. (최댓값)
2. 삭제된 루트 노드에는 Heap의 마지막 노드와 교환.
3. 힙을 재구성.

힙 정렬

• 장점
  • 시간 복잡도가 좋은 편
  • 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 유용
• 시간 복잡도
  • 힙 트리의 전체 높이가 거의 log2n으로 하나의 요소를 힙에 삽입 또는 삭제할 때 힙 재정비하는 시간이 log2n만큼 소요
  • 요소의 개수가 n개
  • T(n) = O(nlog2n)

Java에서의 Priority Queue

MinHeap & MaxHeap

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); 
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); 

출처
https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html
https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)