[알고리즘 자료구조] JavaScript in Heap

1-1. 힙(Heap)

• 힙은 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)이다.
• max - heap과 min - heap 두 가지 타입이 있다.
• 최댓값이 맨 위인 힙을 max - heap, 최솟값이 맨 위인 힙을 min - heap 이라고 한다.
• BST(이진 탐색 트리)와 다르다 => 좌, 우 자식의 대소 관계를 반영하지 않는다 => 층(Level)으로 대소 관계를 구분한다

1-2. 힙(Heap) 규칙

• 큐에는FIFO, 스택은 FILO의 규칙이 있듯 힙(Heap)에도 규칙이 있다.
• Heap Rule: 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 한다.
  따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 한다.

1-3. 배열로 나타낸 힙(Heap)

구현하기 전에 알아야 할 부분이 있다면, 힙(Heap)은 트리를 배열로 나타낼 수 있다는 것이다.
위 이미지에서 Min Heap은 [10, 15, 30, 40, 50, 100, 40], Max Heap = [100, 40, 50, 10, 15, 50, 40 ] 이 된다.
배열로 인해 부모노드, 왼쪽, 오른쪽 자식 노드를 표현할 수 있다.

Min Heap에서 6번째 index를 예로 들어보자.

현재 노드 Index = 6
부모 노드 : Math.floor((자식 노드 Index -1) / 2 ) = 2
왼쪽 자식 노드 Index = (부모노드 * 2) + 1 = 5
오른쪽 자식 노드 Index = (부모노드 * 2) + 2 = 6

구분			부모노드			왼쪽 자식 노드	현재노드, 오른쪽 자식 노드
Index	0	1	2	3	4	5	6
Node	10	15	30	40	50	100	40

따라서 나중에 구현할 때 기본으로 부모, 자식(오른쪽, 왼쪽) 노드들을 아래와 같이 세팅해주게 된다.
이렇게 배열로 나타냄으로서 아래의 표현이 성립하게 된다.

  // 기본 셋팅

  // 부모 노드 Index
  getParentIndex(i) {
    return Math.floor(i - 1 / 2);
  }

  // 자식 왼쪽 노드 Index
  getLeftChildIndex(i) {
    return i * 2 + 1;
  }

  // 자식 오른쪽 노드 Index
  getRightChildIndex(i) {
    return i * 2 + 2;
  }

2. 과정 (max-heap 기준)

힙에는 요소를 삽입할 때와 추출(삭제)할 때 이 두 가지의 구현 방식을 알고 있어야 한다. 설명과 구현은 max-heap을 기준으로 하겠다.
구현하면서 사용했던 주요 함수도 미리 적었다.

2-1. 삽입 알고리즘

1. 원소를 맨 마지막에 넣는다. - push()
2. 부모의 노드와 비교해 더 크다면 자리를 바꾼다. - swap()
3. 현재 노드가 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 의 과정을 반복한다. - heapifyUp()

2-2. 추출 알고리즘

1. 배열의 최상위 노드를 꺼내준다. - maxValue
2. 루트노드와 맨 끝에 있는 원소를 교체한다. - this.data[0] = this.data [this.data.length - 1];
3. 맨 뒤에있는 원소를 (원래 루트 노드)를 삭제한다. > 배열 크기 줄어듦 - this.data.length--;
4. 변경된 노드와 자식 노드들을 비교한다. left, rigth index로 두 자식 간 노드의 크기를 비교하며 루트 노드보다 더 클 경우 자리를 바꿔준다. - heapifyUp(), swap()
5. 자식 노드 둘 보다 부모노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복한다. - heapifyUp()
6. 2에서 제거한 원래 루트 노드를 반환한다. - poll() , return maxValue;

3. 힙 (Heap) 사용 사례

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

1. 우선순위 큐를 구현하는데 사용한다.
2. 게임엔진에서 각 액터의 우선순위를 정한다.
3. 서버에서 많은 트래픽을 처리할 때 우선 처리해야 할 트래픽을 정한다.
4. 시뮬레이션 시스템
5. 네트워크 트래픽 제어
6. 운영 체제에서의 작업 스케쥴링 (우선 순위가 높은 일을 바로 조회할 수 있다.)
7. 수치 해석적인 계산