힙

힙이란?

 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리

완전 이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

힙을 사용하는 이유

 배열에 데이터를 넣고 최대, 최솟값을 찾기 위해선 O(n)이 걸림 이에 반해서 힙에 데이터를 넣고 최대 최소를 찾기위해선 O(logn)이 걸림

우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.

 

힙의 구조

힙은 최댓값을 구하기 위한 구조와 최솟값을 구하기 위한 구조로 분류할 수 있다.

 

힙의 조건

1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(최대 힙)

2. 최소 힙은 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작다.

3. 완전 이진트리 형태이다.

 

 

Max Heap경우 힙에 데이터를 삽입할 때 만약 들어오는 값이 부모 노드보다 값이 클 경우 위치를 swap 한다.

힙은 최대 최솟값을 찾기 위해 고안된 완전 이진트리구조이므로 Max Heap은 루트 노드가 최댓값을 가지고 있다.

주의할 점은 무조건 들어오는 데이터는 최하단부 왼쪽 노드부터 차례대로 채워 진후 swap이 된다는 점이다.

 

힙에서 데이터를 삭제한다는 의미는 데이터를 꺼낸다는 말이다. 일반적으로 최댓값인 루트 노드 값을 가져간다. 이 경우 가장 최하단부 왼쪽에 위치한 노드(일반적으로 마지막에 추가한 노드)를 root노드로 이동한 뒤 swap이 일어난다.

 

 

힙 구현 

 

일반적으로 힙 구현 시 배열 자료구조를 활용함

배열은 인덱스가 0부터 시작하지만 힙 구현 편의를 위해 1부터 시작함

부모 노드 인덱스 = 자식 노드 인덱스 //2

왼쪽 자식 노드 인덱스 = 부모 노드*2

오른쪽 자식 노드 인덱스 = 부모 노드*2 +1

 

힙의 시간 복잡도

n개의 노드를 가지는 heap의 데이터 삽입 삭제 시 최악의 경우 root부터 leaf까지 비교하므로 시간 복잡도는 O(logn)이다