230523 Today I Learned

우선순위큐를 힙으로 구현한다고 하는데 힙에 대해 정확하게 정리해보고자 한다.

힙 (Heap)

참고 사이트

최댓값, 최솟값을 빠르게 찾아내기 위해 고안된 완전이진트리의 자료구조.
모든 노드는 자식 노드보다 우선순위(min/max)가 높거나 같다.
최대힙(max-Heap): 루트노드로 올라갈수록(부모로 올라갈수록) 값이 커지는 구조. 우선순위는 값이 큰 순서대로.
최소힙(min-Heap) : 루트 노드로 올라갈수록(부모로 올라갈수록) 값이 작아지는 구조. 우선순위는 값이 작은 순서대로.

• 특정 요소를 찾는 데는 효율적이지 않으며 일반적으로 최대 최솟값을 빠르게 찾기위해 사용된다.
• 같은 레벨에서 좌우 노드끼리 비교는 고려하지 않는다.
• 이진트리 : 각 노드가 최대 두개의 자식노드를 가진 트리 구조.
• 완전이진트리 : 노드가 왼쪽에서 오른쪽으로 차례대로 채워져있는 이진 트리.

힙에 데이터 삽입

최소힙에서 데이터 삽입 시,
우선순위가 가장 낮다는 가정하에 완전이진트리에서 가장 맨 끝 위치에 저장한 뒤, 부모 노드와 우선순위를 비교해가면서 위치가 맞을때 까지 계속 비교와 위치 조정을 한다.
연산이 트리의 높이에 비례하기 때문에 시간복잡도는 O(log n)이다.

힙에서 데이터 삭제(루트 노드)

우선순위가 가장 높은 루트 노드를 반환하면 가장 마지막 노드를 루트자리에 옮긴 뒤 비교를 통해 위치를 우선순위가 맞을 때 까지 재조정(heapify) 한다.
재조정 과정 때문에 시간복잡도는 O(log n)이다.

• peek은 루트노드만 반환하면 되기 때문에 시간복잡도가 O(1)