[자료구조] 힙(heap)

힙(heap)

최댓값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)

 

* 이진 트리 : 한 노드의 자식 노드가 최대 2개인 트리

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

* 이진 탐색 트리 : 왼쪽 자식 노드 값이 가장 작고, 그 다음은 부모, 그 다음은 오른 쪽 자식 노드가 가장 크다. 

왼쪽: 완전 이진 트리, 오른쪽: 완전 이진 트리아님

 

 

리스트에 데이터를 넣고, 최댓값과 최소값을 찾을 때 시간 복잡도 : O(n)

힙에 데이터를 넣고, 최댓값과 최소값을 찾을 때 시간 복잡도 : O(logn)

 

 

최소힙 (Min Heap) 

각 노드의 값이 자식 노드보다 작거나 같다.  

자식 노드 값은 오른쪽이 클수도, 왼쪽이 클수도 있다. 

 

최소 힙

 

 

위의 힙을 리스트의 형태로 구현하면 [-, 1, 2, 5, 6, 7, 8, 9] 된다. 

루트 -> list[1] # 인덱스 1번

왼쪽 자식 인덱스 = 부모 인덱스 * 2
오른쪽 자식 인덱스 = 부모 인덱스 * 2 + 1
부모 인덱스 = 자식 인덱스 / 2

 

최소힙 삽입

1. 가장 마지막 노드에 삽입

2. 부모 노드와 크기 비교 부모 노드보다 작다면 부모 노드와 자리 교환, 크다면 그 자리에서 정지

3. 교환 후 다시 부모 노드와 크기 비교 (반복)

 

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]
None	1	2	5	6	7	8	9
None	1	2	5	6	7	8	9	3	부모와 크기 비교 후 자리 변경
None	1	2	5	3	7	8	9	6	부모가 더 작아서 자리 변경 없음

 

 

최소힙 삭제

1. 루트 노드 삭제, 마지막 원소를 루트로 이동

2. 작은 값을 가진 자식과 위치를 교환

3. 교환 후 다시 작은 값을 가진 자식과 위치 교환 (반복)

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
None	1	2	5	6	7	8	9	루트 노드 삭제 후 마지막 원소를 루트로 이동
None	9	2	5	6	7	8		자식 노드와 비교 후 교환 (2가 5보다 작음)
None	2	9	5	6	7	8
None	2	9	5	6	7	8		자식 노드와 비교 후 교환 (6이 7보다 작음)
None	2	6	5	9	7	8		더 이상의 자식 노드가 없음

 

최대힙(Max Heap)

각 노드의 값이 자식 노드보다 크거나 같다. 

(다른 내용은 최소 힙과 흡사함)