[알고리즘] 힙 (Heap) - 최소힙, 최대힙

힙 (Heap)

• 최댓값이나 최솟값을 빠르게 하기 위해서 고안된 완전 이진트리(왼쪽부터 추가하는 구조)를 기본으로 한 자료구조이다.
• 트리 구조를 기반으로 한 구조 방식이라고 생각하면 된다.

 

🥇 최소힙, 최대 힙

최소 힙은 작은 값을 항상 트리의 위에 두어, root에 가장 작은 값이 온다. 그렇기에 자식의 부모 요소는 자식보다 작다.

최대 힙은 가장 큰 값을 항상 트리의 위에 두어, root에 가장 큰 값이 온다. 그렇기에 자식의 부모요소는 자식보다 크다.

 

🥇 최소 힙에 노드 추가하기

1. 완전 이진트리에 맞게 맨 마지막 레벨에 왼쪽부터 노드를 추가해준다.
2. 추가한 노드의 값과 부모 요소를 비교하여 더 작으면 자리를 바꾼다. 부모 노드보다 작도록 반복한다.
3. 한번 돌 때마다 절반식 경우가 줄어들기에 시간 복잡도는 O(log n)이다

 

🥇 최소 힙에 가장 작은 노드 꺼내오기

1. 가장 작은 값은 root의 값이기에 쉽게 꺼내 올 수 있다.
2. 하지만 root가 빠지면 빈자리를 채워주어야 하기에, 완전 이진트리에 맨 마지막 노드를 꺼내서 root를 채워준다.
3. root를 자식 노드와 비교해서 더 작은 노드와 바꾼다. 반복한다.
4. 한번 돌 때마다 절반식 경우가 줄어들기에 시간 복잡도는 O(log n)이다.

 

출처

해당 게시글에 사용된 모든 이미지의 저작권은 유튜브 엔지니어 대한민국에 있습니다.

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