heap이란 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해서 고안된,
완전 2진 트리를 기본으로한 자료구조 이다.
heap은 규칙에 따라서 크게 max heap과 min heap으로 나눌 수 있는데,
max heap: 부모 노드는 항상 자식 노드보다 크거나 같아야 함.
min heap: 부모 노드는 항상 자식 노드보다 작거나 같아야 함. 이고,
힙 전체를 통틀어 이 규칙은 꼭 유지 되어야 해.
min heap에 대해서 얘기를 해보자면,
root에는 가장 작은 값이 들어가고, 그 아래로 완전 2진 트리의 형식으로 값들이 채워지게 되어있어.
각각의 노드는 자기 부모 노드보다 작은 값을 가질 수 없게 되어 있지, 즉 자기 부모보다만 작은 값을 가진다면 상위에 있는 다른 노드보다 작은 값을 가질 수도 있다는 얘기야! 나는 이 부분이 조금 했갈렸기 때문에 당연한 얘기를 한번 더 써봤어.
만약 min heap의 자료 구조에 새로운 값이 들어오게 된다면 맨 마지막 노드에 그 값을 넣고, 자신의 부모와 비교해서 부모가 더 크면 부모의 값을 밑으로 내려 이 과정을 부모가 더 작을때 까지 반복하는 형식으로 정렬을 하면 되는거야 참 쉽지? 이런 heap구조를 사용해서 정렬을 하게 되면 (nlog₂n)의 시간이 걸리게 되는데, 그냥 삽입정렬, 선택 정렬을 했을때의 시간 복잡도 n | n^2 보다 훨씬 빠르게 연산을 끝낼 수 있게되지.
오늘의 공부는 여기서 마치고, 이 알고리즘을 구현해서 git hub에 올려보도록 할게
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 알고리즘 연습 프로그래머스 - 완주하지 못한 선수 (0) | 2021.10.14 |
|---|---|
| 알고리즘 풀이 -3 프로그래머스 heap 문제 "더 맵게" (0) | 2021.10.10 |
| 알고리즘 연습 프로그래머스 스택 - 큐 기능개발 문제 풀이 (0) | 2021.10.07 |
