알고리즘/자료구조

[알고리즘, 자료구조] 힙 Heap 자바스크립트로 구현하기

AlgoRoot 2022. 3. 25. 22:48
반응형

 

오늘 배운 자료구조는 힙(Heap)이다. 

개념 정리는 항해 99측 강의 자료를 기반으로 썼고, 추가적인 사항은 구글링을 통해 덧붙였다. 

힙(Heap) 구현은 자바스크립트로 하기 위해서 유튜브를 참고했다. 

 

강의에서는 파이썬으로 다루는데 결국에는 heap도 내장모듈이 있어 굉장히 편리해보였다.

백준에서 힙관련 알고리즘을 풀어봤는데 구현을 처음부터 해야함에 있어서 꼭 알고 있어야겠다는 생각이들었다.

반면 파이썬으로 푼 답을 보니 다섯줄정도였나..? 아무튼 내장모듈을 써서 코드가 짧았다. 

 

값을 추출하는 poll()부분을 이해하는데 애를 먹었고 경우의 수 하나하나 노트에 그려보며 이해하는 과정을 거쳤다. 

 

 

 

힙 (Heap)

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

 

 

힙(Heap) 규칙

큐에는 FIFO, 스택은 FILO의 규칙이 있듯  힙(Heap)에도 규칙 있다. 

Heap Rule : 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 한다.

 

따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 한다. 

 

 

 

 

배열로 나타낸 힙(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;
  }

 

 

 

 

과정 (max-heap 기준)

힙에는 요소를 삽입할 때와 추출(삭제)할 때 이 두 가지의 구현 방식을 알고 있어야 한다. 설명과 구현은 max-heap을 기준으로 하겠다. 

구현하면서 사용했던 주요 함수도 미리 적었다. 

 

 

삽입 알고리즘 

1. 원소를 맨 마지막에 넣는다. - push()

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

3. 현재 노드가 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 의 과정을 반복한다. - heapifyUp()

 

 

추출 알고리즘

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;

 

 

힙 (Heap) 사용 사례

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

 

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

 

 

 

JavaScript 로 힙(Heap) 구현

 

1. 기본 골격

위에서 미리 설명한 부분이다. 부모의 Index, 자식 Index를 left와 right로 구분한다. 

또 노드끼리 비교 후 index를 서로 바꿔주는 swap() 메서드를 만들어 준다.

 

// 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;
  }

}

 

 

2. push()

삽입 알고리즘 

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

 

여기서 핵심은 push() 메서드 안에 있는 heapifyUp()이다.  이 함수를 통해 Max-Heap 형태를 갖추도록 조정된다.

 

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

 

 

3. heapifyUp() 

max-heap에 맞게 제일 큰 노드는 트리의 최상단 즉 배열의 첫번째 값으로 해주기 위해 방금 들어온 노드의 위치를 변수로 둔다. 

 

1. currentIndex : 최근에 삽입된 노드의 Index
2. while문 : currentIndex의 요소가 상위요소보다 클 때까지 돌린다. 
현재 요소 ( 가장 마지막, 밑에있던 요소)와 부모 요소의 값을 비교한다. 현재 요소가 크면 위로 올려야 하기 때문에 swap()을 쓴다. 
3. 비교를 거친후 새 위치에 대해 이를 반복해야 하므로 currentIndex를 비교했던 부모 요소의 Index로 재할당시 킨다. 
  // 인자 필요없다 항상 배열의 마지막 요소를 다루기 때문
  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);
    }
  }

 

 

 

4. poll() 추출 

최댓값을 꺼내는 추출하는 법을 알아보겠다.  역시 여기서도 heap규칙을 지키기 위한 heapifyDown()함수가 중요하다.

 

추출 알고리즘

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;

 

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

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

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

    return maxValue;
  }

 

 

 

5. heapifyDown() 

1. currentIndex : 최상위 노드를 지정한다. 
2. while문 : 최상위에 있는 현재 노드보다 자식 노드가 더 크면 현재 노드와 자식 노드를 바꿔주는 while문을 반복한다.
(이때 왼쪽 노드를 기준으로 비교 검사할 것이기 때문에 왼쪽 노드가 있을 때까지 라는 조건을 넣어준다.)
3. biggestChildIndex : currentIndex = 0 일 때 부 자식의 왼쪽 노드의 Indexr값을 변수로 지정해준다. 
4.  만약 자식의 오른쪽 노드가 있고, 자식의 오른쪽 노드가 왼쪽 노드보다 크다면 3. 의 date [biggestChildIndex]를 자식의 오른쪽 노드로 지정해준다. 

5. 4. 의 조건이 불충분하면 자식의 왼쪽 노드가 더 크다는 뜻이므로 현재 heap배열의 최상단 노드가 date [biggestChildIndex](자식 왼쪽 노드) 보다 큰지 비교해준다. 

6. date [biggestChildIndex]가 더 크다면 swap()을 통해 서로 간의 노드 위치를 바꿔준다. 
7. 이후 새로운 위치에서의 비교 연산을 위해 currentIndex를 biggestChildIndex로 바꿔준다. 

이 함수가 끝나면 다시 poll()로 돌아가게 되고 최종적으로 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;
      }
    }
  }

 

 

힙(Heap)의 Big-O (Time Complexity)

 

삽입 : 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올린다. 

완전 이진트리의 최대 높이는 O(logN)이고, 반복하는 최대 횟수도 O(logN)이 된다. 

 

삭제(추출) : 원소를 맨 위 넣어서 바닥까지 비교하면서 올린다.

완전 이진트리의 최대높이는 O(logN)이고, 반복하는 최대횟수도 O(logN)이된다. 

 

 

Big-O (시간복잡도) 삽입 추출, 삭제
힙 (Heap) O(logN) O(logN)

 

 

최종 구현 코드

주석이 많아서 그렇지 구현하고 보니 결국에는 간단한 로직인 것 같다는 생각이 든다. 

// 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;
      }
    }
  }
}

 

테스트 완료 !

 

 

 

 

빼놓을 수 없는 스택(Stack) 자료구조 이해 & 구현하기!

 

[알고리즘, 자료구조] 자바스크립트로 스택(Stack)구현하기

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 한다. 그 중 널리 사

algoroot.tistory.com

 

큐(Queue) 자료구조 이해 & 구현하기!

 

[알고리즘, 자료구조] 자바스크립트로 큐(Queue)구현하기 (+개념이해)

지난 스택(Stack)편에 이어 이번 시간에는 큐(Queue)에 대해 알아보겠다. 스택(Stack) 편 link https://algoroot.tistory.com/54 [알고리즘, 자료구조] 자바스크립트로 스택(Stack)구현하기 어떤 데이터의 구체적..

algoroot.tistory.com

 

 

 

Reference

- 항해 99 강의자료 일부

- https://www.youtube.com/watch?v=hzxa4psfxxg 

 



반응형