힙 (Heap)

#자료구조

힙은 트리 (Tree)기반의 자료 구조이며, 완전 이진 트리의 일종이다. 수의 집합에서 가장 큰 수와, 가장 작은 수를 빠르게 찾기 위해 만들어진 자료구조다.

예를 들어 다음과 같은 배열이 있다고 해보자.

let arr = [1, 2, 3, 4, 5, 6, 7, 8 ,9];

이 배열에서 최댓값을 구하기 위해선 배열을 모두 돌아야 하므로 시간 복잡도는 O(n)을 가지게 된다. 하지만 힙을 이용하면 이 작업을 log(n)으로 해결할 수 있다.

특징

부모 노드의 값이 자식 노드의 값보다 크거나 같은 힙이다. 즉, 루트 노드가 최댓값이다.

힙의 구현은 주로 배열을 이용한다. 배열에 루트 노드부터 넣고, 아래로 내려가면서 부모 노드를 왼쪽에서 오른쪽으로 넣어준다.

새로운 요소가 들어오면 힙의 마지막 노드, 즉 배열의 마지막 인덱스에 넣는다.

새로 삽입된 노드는 자신의 부모 노드와 값의 크기를 비교하면서 자신보다 크거나 같은 노드를 만날 때 까지 부모 노드와 위치를 바꾸며 이동한다.

최대 힙에서의 삭제는 가장 큰 값 즉, 루트 노드를 제거하는 것이다. 루트 노드를 제거한 후 가장 마지막 노드를 루트 노드로 올린다.

그리고 루트 노드는 자식 노드 중 자신보다 큰 자식 중에서도 값이 더 큰 자식 노드와 자리를 바꾸면서 바뀌지 않을 때 까지 내려간다.

최대 힙과 반대로 루트 노드가 가장 작은 값이다.
삽입과 삭제는 최대 힙의 방식과 같은 방식으로 진행한다.