Heap

Heap 이란?

-특정한 조건을 만족하도록 구성된 Complete Binary Tree(완전 이진 트리)
-Heap에는 Max Heap(최대 힙), Min Heap(최소 힙) 두가지 종류가 있음
-Heap은 Prioruty Queue(우선순위 큐)를 구현하는데 사용됨

Heap의 특징

1. 완전 이진 트리 : Heap은 항상 완전 이진 트리의 형태를 유지. 이는 트리가 왼쪽에서 오른쪽으로 채워져야 한다는 의미를 가짐.

2. Heap 속성
   -Max Heap(최대 힙) : 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같음
   -Min Heap(최소 힙) : 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같음

Heap의 주요 연산

1. 삽입
   -새로운 요소를 Heap의 마지막에 추가
   -Heap 속성이 유지되도록 요소를 위로 이동시킴(Heapify Up)

2. 삭제
   -Max Heap에서는 루트 노드(최대값)를 삭제하고, Min Heap에서는 루트 노드(최소값)를 삭제
   -마지막 노드를 루트 노드로 이동시키고, Heap속성이 유지되도록 요소를 아래로 이동시킴(Heapify Down)

3. Heap 생성
   -주어진 배열을 Heap으로 변환
   -일반적으로 Heapify Down 을 반복적으로 호출하여 배열을 Heap구조로 만듬

Heap의 구현

Heap은 배열을 사용하여 구현가능
-왼쪽 자식의 인덱스는 2 * i + 1
-오른쪽 자식의 인덱스는 2 * i + 2
-부모의 인덱스는 (i - 1) / 2

Heap의 시간복잡도

-삽입 : O(log n)
-삭제 : O(log n)
-최대값 / 최소값 추출 : O(log n)
-heap 생성 : O(n)

Heap을 사용하기에 유용한 상황

-우선순위 큐(Prioruty Queue) : 작업이나 이벤트가 우선순위에 따라 처리되어야 하는 경우
-힙 정렬(Heap Sort) : 배열을 정렬하는 알고리즘
-최대값 / 최소값 문제 : 주어진 범위에서 최대값이나 최소값을 빠르게 찾아야 하는 경우
-효율적인 삽입 및 삭제 연산을 제공하므로, 우선순위 큐나 실시간 데이터 스트림에서 주로 사용됨