[자료구조]이진 힙(Binary Heap)

Heap이란?

최대값이나 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리를 기본으로 한 자료구조이다. 

기본적인 종류에는 Min Heap과 Max Heap이 존재한다. 

 

Min Heap과 Max Heap

Min Heap은 작은값이 항상 위에 있게 그리고 Max Heap은 가장 큰값이 위에 있는 힙이다.

기본적으로 노드 삽입이나 노드 꺼내오는 방식은 Min Heap이나 Max Heap은 같다.

 

Min Heap노드 삽인

1. Tree가 Complete BInary의 형태를 잃지 않게 노드를 왼쪽부터 채워나감

2. 처음 삽입시 정렬된 상태가 아니다.

3. 삽입된 노듣가 값이 작으면 부모노드와 자리를 바꾼다.

4. 3번의 작업을 부모노드 값이 삽입된 노드의 갓ㅂ보다 작을 때까지 혹은 Root에 도달할때 까지 진행한다.

=> 시간 복잡도는 O(logn)

 

Min Heap 노드 꺼내오기

Root Node를 꺼낸다 가정

1. Root Node를 꺼낸다.

2. 맨 마지막 노드를 Root Node자리에 채운다.

3. root Node에 채운 노드를 자식노드와 비교해 더 작은 놈과 자리를 바꾼다. 

4. 3번의 작업을 자식노드가 더 크거나 그 바뀌고 있는 노드가 leaf node에 도달하면 멈춘다.

=> 시간복잡도 O(logn)

 

 

 

 

참고자료

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#tree

https://www.youtube.com/watch?v=jfwjyJvbbBI&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP&index=3