[자료구조] 트리(Tree) - 이진 힙(Binary Heaps)

아래의 유툽영상을 바탕으로 작성되었습니다. 좋은영상 감사합니다.

Binary Heaps (Min-Heaps and Max-Heaps) - https://youtu.be/jfwjyJvbbBI

0. 힙(Heaps)란?

최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리를 기본으로 한 자료구조.

root에 가장 작은 값이 오면 최소 힙(min heap), root에 가장 큰 값이 오면 최대 힙(max heap)

 

1. 최소 힙에 노드 삽입하기(Insert)

1. 완전 노드의 맨 끝(leaf)에 노드를 추가하되, 완전 이진 트리(Complete binary tree)를 유지해야 하므로 마지막 레벨의 왼쪽부터 추가.

2. 부모노드 > 새노드 라면 부모와 새노드의 자리를 바꿈.

3. 부모노드 < 새노드거나, 새노드가 root가 될때까지 반복.

 

*한 레벨씩 연산하므로 시간복잡도는 O(logn)*

 

2. 최소 힙에서 노드 꺼내오기(Delete)

1. root를 꺼낸 뒤, 제일 마지막 노드를 root자리로 이동시킴.

2. root와 left child, right child를 비교해서 더 작은 자식과 스왑한다.

3. 스왑한 노드의 자식들이 현재 노드보다 크거나, leaf 노드일때 까지 반복한다.

 

*한 레벨씩 연산하므로 시간복잡도는 O(logn)*

 

3. 이진 힙의 구현 및 연습(c++)

벡터를 이용한 이진 힙 구현.

(연습용으로 구현한 코드입니다. 잘못된 부분이 있으면 언제든 알려주세요. 감사합니다 (--)(__))

 

(1) .h

(2) .cpp