힙(Heap)이란?
힙은 최대값, 최소값을 찾아내는 연산을 쉽게 하기 위해서 고안된 완전 이진트리로 구성된
자료구조 이다.
(여기서 완전 이진트리란 자식 노드를 왼쪽부터 오른쪽으로 채워 넣는것을 뜻한다)
Heap에는 두가지가 있다.
1. 최소 Heap
2. 최대 Heap
각각에 대해서 알아보자.
1. 최소 Heap
최소 Heap은 말 그래도 값이 작은 값을 항상 부모 노드로 올림으로써 루트에는
항상 가장 작은 값이 오도록 하는것을 뜻한다.
2. 최대 Heap
최대 Heap은 최소 Heap과는 반대로 가장 큰값을 부모노드로 계속 올림으로써
루트에는 항상 가장 큰값이 오도록 하는것을 뜻한다.
최소 Heap의 노드 삽입 과정
1. 1 삽입
2. 부모 노드와 확인후 작으면 부모노드와 변경
3. 또 부모 노드보다 작다면 2 에서 했던거 반복
최소 Heap의 노드 추출 과정
1. 1을 뺀다
2. 가장 마지막 노드인 3을 root로 넣는다.
4. 자식이 부모보다 크니 자식중 작은 노드를 부모 노드로 올린다.
(최대 Heap도 최소 Heap과 같은 방식이다.)
위의 과정들을 배열로 나타내 본다면 아래와 같다.
최소 Heap의 노드 삽입 과정
1. 1 삽입
0 1 2 3 4
| 2 | 4 | 3 | 5 | 6 |
0 1 2 3 4 5
| 2 | 4 | 3 | 5 | 6 | 1 |
2. 부모 노드와 확인후 작으면 부모노드와 변경
여기서는 1의 index인 5를 부모 노드인 4의 index인 2로 수정해줘야 하는데
자식 -> 부모 로 index를 바꾸는 공식은 아래와 같다.
자식 -> 부모
자식 index -1 / 2
위의 상황을 대입해서 보자면 아래와 같다.
5-1 / 2 = 4/2 = 2
그렇게 되면 node는 아래와 같이 변하게 된다.
0 1 2 3 4 5
| 2 | 4 | 1 | 5 | 6 | 3 |
이렇게 되면 또 1과 2를 서로 바꿔줘야 한다.
2-1/2 = 1/2 = 0
| 1 | 4 | 2 | 5 | 6 | 3 |
이렇게 삽입이 되는 방식이다.
이처럼 자식에서 부모로 가는 공식도 있지만 부모에서 자식노드로 가는 공식도 있다.
부모 -> 왼쪽 자식
2 * index + 1
0 1 2 3 4 5
| 1 | 4 | 2 | 5 | 6 | 3 |
위로 예를 들자면 4의 왼쪽 자식은 5이다.
index 1 -> index 3으로 가야하는데 방식은
2 * 1 + 1 = 2 + 1 = 3
부모 -> 오른쪽 자식
2 * index + 2
0 1 2 3 4 5
| 1 | 4 | 2 | 5 | 6 | 3 |
위의 배열로 예를 들자면 4의 오른쪽 자식은 6이다.
index 1 -> index 4으로 가야하는데 방식은
2 * 1 + 2 = 2 + 2 = 4
그럼 최소 Heap의 추출 방식을 배열로 표현해보자.
최소 Heap의 노드 추출 과정
1. 1 추출
0 1 2 3 4 5
| 4 | 2 | 5 | 6 | 3 |
2. 가장 마지막 노드를 Root로 올리기
index 5 -> index 0
0 1 2 3 4
| 3 | 4 | 2 | 5 | 6 |
3. 자식 노드중 작은 2를 부모 노드인 3과 바꿔야 함
index 2 -> index 0
2-1/2 = 1/2 = 0
0 1 2 3 4
| 2 | 4 | 3 | 5 | 6 |
이처럼 우리가 최소 Node와 최대 Node를 추출 및 삭제를 하는 과정에서 걸리는 과정은
반씩 줄어들게 된다 따라서 시간 복잡도는 아래와 같다.
시간 복잡도 = O( log n)
'코딩일기 > 알고리즘' 카테고리의 다른 글
| [프로그래머스 : 레벨 3] 디스크 컨트롤러 : PriorityQueue(Java) (0) | 2021.05.30 |
|---|---|
| [프로그래머스 : 레벨 2] 더 맵게 (feat. PriorityQueue , Java) (0) | 2021.05.28 |
| [프로그래머스 : 레벨2] 주식가격 (Java) (0) | 2021.05.27 |
| [프로그래머스 : 레벨 2] 다리를 지나는 트럭 : Queue(Java) (0) | 2021.05.26 |
| [프로그래머스 : 레벨2] 프린터(java) (0) | 2021.05.22 |
