[자료구조] Heap

Heap

부모 노드의 값이 자식 노드보다 항상 큰(또는 작은) 완전 이진 트리

그림을 보면 쉽게 이해할 수 있다.

이를 리스트로 표현하면 더욱 쉽게 이해할 수 있다.

왜 쓰는 걸까?

1. max (or min) 값이 루트에 위치

기본적으로 자료구조 내의 값에서 최댓값 또는 최솟값은 항상 트리의 루트에 위치하게 된다.

해당 값을 찾아내는 연산은 O(1)로 고정된다.

1. 매우 효율적인 삽입, 삭제 연산

힙은 완전 이진 트리 구조이므로 이전 높이와 다음 높이의 노드의 수는 두 배가 된다.

높이가 h일 때, 최소 노드 수는 2^(h-1)이고, 최대 노드 수는 2^h - 1이다.

예컨데, 8레벨 까지 모든 노드가 들어찬 255개의 값이 있는 트리에서는

값의 삽입과 삭제에 힙의 높이만큼의 연산이 필요하므로

시간 복잡도가 O(logN)이 된다.

만약 정렬된 리스트에 새로운 값을 추가하기 위해 값을 비교하고,

해당 위치에 값을 삽입한 뒤에는 해당 인덱스 이후의 값을 한 칸씩 뒤로 옮겨야 하므로

최악의 경우 시간 복잡도는 O(N)이 된다.

값의 삽입과 삭제가 매우 빠르고 효율적이라는 것이 heap의 가장 큰 장점이다.