자바스크립트에서 힙 구현하기

• https://nyang-in.tistory.com/153

• 힙 : 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조

• 힙에는 최소힙과 최대힙이 있다

• 최소힙 : 작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 한다

• 최대힙 : 가장 큰 값이 맨 위에 오도록 한다. 모든 노드는 자기 부모 노드보다 작다

힙에 데이터를 삽입하고 값을 꺼내오기

최소힙에 데이터를 삽입하는 방법

1. 위와 같은 트리가 있다고 하자
2. 1을 삽입하려고 할 때 완전이진트리의 조건을 만족시키려면 '3' 아래에 삽입해야 한다
3. 그 다음 자신의 값과 부모노드값을 비교하여 자신의 값이 더 작으면 자리를 바꾼다
4. 자신의 값이 부모 노드 값보다 작을 때까지 혹은 루트에 도달할 때 까지 반복한다
5. 이 작업은 완전이진트리에서 리프노드에서 한 레벨씩 루트까지 올라가는 것으로보면 최대 O(log(n))의 시간복잡도를 가진다

최소힙에서 최솟값 꺼내기

1. 최솟값은 당연히 루트에 있다 => 루트 노드의 값을 꺼낸다
2. 루트 노드가 비었으니 이제 채워야 한다. 트리의 맨 마지막 노드를 가져온다
3. 가져오니깐 정렬이 되어있지 않다. 자식 노드와 비교해서 자기보다 작은 노드와 자리를 바꾼다
4. 자식 노드가 자신보다 크거나 리프노드에 도달할 때 까지 반복한다
5. 이 작업은 루트에서 한 레벨씩 최대 리프노드 까지 내려가므로 최대 O(log(n))의 시간복잡도를 가진다

힙은 배열로 구현

• 다른 자료구조와 달리 힙은 자식에 대한 포인터를 갖는 대신에 배열을 사용해서 자료를 저장한다
• 배열의 인덱스는 각 항목의 차수/높이를 정의한다
• 배열의 첫 번째 항목을 루트로 정한 다음 각 왼쪽 항목과 오른쪽 항목을 순서대로 채움으로써 이진 힙을 다룰수 있다

• 위의 그림 속 힙의 경우 배열은 [2, 4, 23, 12, 13]이 된다

이진 힙 배열 인덱스 구조

• 자신 : N
• 부모 : (N - 1) / 2 => 소숫점은 버린다
• 왼쪽 자식 : 2N + 1
• 오른쪽 자식 : 2N + 2