힙

요약

• 힙은 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조
• 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

• 힙은 대게 최대 힙과 최소 힙 두 가지 종류로 구분된다.
• 최소힙 : 값이 낮은 데이터가 먼저 삭제
• 최대힙 : 값이 높은 데이터가 먼저 삭제

• 힙은 삽입과 삭제에 O(NlogN)의 시간 복잡도를 가진다.

힙 사용 사례

• 우선순위 큐를 구현하는데 사용한다.

• 게임엔진에서 각 액터의 우선순위를 정한다.

• 서버에서 많은 트래픽을 처리할 때 우선 처리해야 할 트래픽을 정한다.

• 시뮬레이션 시스템

• 네트워크 트래픽 제어

• 운영 체제에서의 작업 스케쥴링 (우선 순위가 높은 일을 바로 조회할 수 있다.)

• 수치 해석적인 계산

힙의 종류

• 최대 힙 : 부모 노드가 항상 자식 노드보다 크거나 같은 속성을 갖는 이진 트리

• 최소 힙 : 부모 노드가 항상 자식 노드보다 작거나 같은 속성을 갖는 이진 트리

JS로 힙 구현

// max heap 구현

class Heap {
  constructor() {
    this.data = [];
  }

  // 기본 셋팅
  getParentIndex(i) {
    return Math.floor(i - 1 / 2);
  }

  getLeftChildIndex(i) {
    return i * 2 + 1;
  }

  getRightChildIndex(i) {
    return i * 2 + 2;
  }

  swap(i1, i2) {
    const temp = this.data[i1];
    this.data[i1] = this.data[i2];
    this.data[i2] = temp;
  }

}

삽입과 삭제

1. 원소를 맨 마지막에 넣는다.

2. 부모의 노드와 비교해 더 크다면 자리를 바꾼다.

3. 현재 노드가 부모 노드보다 작거나 가장 위에 도달하지 않을때까지 2번을 반복한다.

class Heap {
 ...
  // push 배열 끝에 넣기
  push(key) {
   this.data[this.data.length] = key;
   // 가장 큰 값일 수 있다. heap요구사항에 따라 자리를 바꿔줘야함 > hepifyUp()통해서 이뤄진다.
   this.heapifyUp();
  }

	// 인자 필요없다 항상 배열의 마지막 요소를 다루기 때문
  heapifyUp() {
    let currentIndex = this.data.length - 1;

    // current요소가 상위요소보다 클 때까지 돌린다.
    // 현재 요소 (가장마지막, 밑에있던 요소) 와 부모 요소의 값을 비교 한다. 
    // 현재요소가 크면 위로 올려야하기 때문에 swap()을 쓴다.
    while (
      this.data[currentIndex] > this.data[this.getParentIndex(currentIndex)]
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));

      // currentIndex를 비교했던 부모요소로 재할당시킨다.
      currentIndex = this.getParentIndex(currentIndex);
    }
  }
}

class Heap {
...

	poll() {
    // 가장 최상단 요소가 최댓값일 테고
    const maxValue = this.data[0];

    // 그 최상단 요소와 가장 아래에있는 요소로 대체한다. (제거해도되는데 여기서는 대체함)
    this.data[0] = this.data[this.data.length - 1];
    // 배열의 길이를 줄여 맨위에 할당했던 마지막 요소를 없애준다.
    this.data.length--;

    // 여전히 heap의 규칙인지 확인해야한다.
    // 이때 위에서부터 제일 아래로 실행되는 heapifyDown함수 실행
    // 위에서 끝에있던 요소를 첫번째로 대체했었기 때문에
    this.heapifyDown();

    return maxValue;
  }

	heapifyDown() {
    // index 0 최상위 요소
    let currentIndex = 0;

    // 현재 요소를 맨위에 놓고 자식이 더 크면 현재와 자식을 바꿔주는 while문 반복

    // 왼쪽 요소가 있는지 확인
    while (this.data[this.getLeftChildIndex(currentIndex)] !== undefined) {
      let biggestChildIndex = this.getLeftChildIndex(currentIndex);

      if (
        this.data[this.getRightChildIndex(currentIndex)] !== undefined &&
        this.data[this.getRightChildIndex(currentIndex)] >
          this.data[this.getLeftChildIndex(currentIndex)]
      ) {
        biggestChildIndex = this.getRightChildIndex(currentIndex);
      }

      if (this.data[currentIndex] < this.data[biggestChildIndex]) {
        this.swap(currentIndex, biggestChildIndex);
        currentIndex = biggestChildIndex;
      } else {
        return;
      }
    }
  }

}

1. 배열의 최상위 노드를 꺼내준다.

2. 루트 노드와 맨 끝 원소를 교체한다.

3. 맨 뒤에 있는 원소를 삭제한다. → 배열 크기 줄어듦

4. 변경된 노드의 자식 노드들을 비교한다.
1. left, right, index로 두 자식간 노드의 크기를 비교하며 루트 노드보다 클 경우 자리를 바꿔준다.

5. 자식 노드 둘 보다 부모노드가 크거나 가장 바닥에 도달하지 않을때까지 3번을 반복한다.

6. 2번에서 제거한 루트 노드를 반환한다.

최종 구현 코드

// max heap 구현

class Heap {
  constructor() {
    this.data = [];
  }

  // 기본 셋팅
  getParentIndex(i) {
    return Math.floor(i - 1 / 2);
  }

  getLeftChildIndex(i) {
    return i * 2 + 1;
  }

  getRightChildIndex(i) {
    return i * 2 + 2;
  }

  swap(i1, i2) {
    const temp = this.data[i1];
    this.data[i1] = this.data[i2];
    this.data[i2] = temp;
  }

  // push 배열 끝에 넣기
  push(key) {
    this.data[this.data.length] = key;
    // 가장 큰 값일 수 있다. heap요구사항에 따라 자리를 바꿔줘야함 > hepifyUp()통해서 이뤄진다.
    this.heapifyUp();
  }

  // 인자 필요없다 항상 배열의 마지막 요소를 다루기 때문
  heapifyUp() {
    let currentIndex = this.data.length - 1;

    // current요소가 상위요소보다 클 때까지 돌린다.
    // 현재 요소 (가장마지막, 밑에있던 요소) 와 부모 요소의 값을 비교 한다. 현재요소가 크면 위로 올려야하기 때문에 swap()을 쓴다.
    while (
      this.data[currentIndex] > this.data[this.getParentIndex(currentIndex)]
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));

      // currentIndex를 비교했던 부보요소로 재할당시킨다.
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  // Push 뿐만아니라 poll도 할 줄 알아야 함(추출)

  poll() {
    // 가장 최상단 요소가 최댓값일 테고
    const maxValue = this.data[0];

    // 그 최상단 요소와 가장 아래에있는 요소로 대체한다. (제거해도되는데 여기서는 대체함)
    this.data[0] = this.data[this.data.length - 1];
    // 배열의 길이를 줄여 맨위에 할당했던 마지막 요소를 없애준다.
    this.data.length--;

    // 여전히 heap의 규칙인지 확인해야한다.
    // 이때 위에서부터 제일 아래로 실행되는 heapifyDown함수 실행
    // 위에서 끝에있던 요소를 첫번째로 대체했었기 때문에
    this.heapifyDown();

    return maxValue;
  }

  heapifyDown() {
    // index 0 최상위 요소
    let currentIndex = 0;

    // 현재 요소를 맨위에 놓고 자식이 더 크면 현재와 자식을 바꿔주는 while문 반복

    // 왼쪽 요소가 있는지 확인
    while (this.data[this.getLeftChildIndex(currentIndex)] !== undefined) {
      let biggestChildIndex = this.getLeftChildIndex(currentIndex);

      if (
        this.data[this.getRightChildIndex(currentIndex)] !== undefined &&
        this.data[this.getRightChildIndex(currentIndex)] >
          this.data[this.getLeftChildIndex(currentIndex)]
      ) {
        biggestChildIndex = this.getRightChildIndex(currentIndex);
      }

      if (this.data[currentIndex] < this.data[biggestChildIndex]) {
        this.swap(currentIndex, biggestChildIndex);
        currentIndex = biggestChildIndex;
      } else {
        return;
      }
    }
  }
}