[자료구조] - 힙(heap)

Seong Hyeon Kim·2022년 10월 7일
0

CS스터디

목록 보기
7/9

1.힙(Heap)의 정의

1-1 힙이란?

맨 처음에 힙을 들었을 때 엉덩이(hip)가 생각날 수도 있지만

힙은 heap이다. 무언가를 차곡차곡 쌓아 올린 더미라는 뜻이다.

힙(Heap)은 완전이진트리의 형태로 만들어진 자료구조이다.

돌더미, 작장더미, 쓰레기 더미 등등 위로 갈수록 노드의 수가 줄어드는 모습을 하고 있다.


힙(Heap) 의 특징

  • 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

  • 힙은 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 이다.

  • Max-heap 과 Min-heap 두 가지 타입이 있다.

  • 최댓값이 맨 위인 힙을 Max-heap, 최솟값이 맨 위인 힙을 Min-heap이라고 한다.

  • BST(이진 탐색 트리)와 다르다. 좌, 우 자식의 위치가 대소 관계를 반영하지 않는다. (층(level)으로 대소 관계를 구분한다.)

  • 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

  • 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도이고 간단하게 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.

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


2. 힙(Heap)의 종류

최대 힙(Max Heap): (완전 이진 트리) + (부모 노드 > 자식 노드)
최소 힙(Min Heap): (완전 이진 트리) + (부모 노드 < 자식 노드)

  • 최대 힙은 완전 이진 트리이면서 부모 노드가 자식 노드보다 큰 트리

  • 최소 힙은 완전 이진 트리이면서 부모 노드가 자식 노드보다 작은 트리이다.

  • 쉽게 말해 최댓값이 맨 위인 힙을 Max-heap // 최솟값이 맨 위인 힙을 Min-heap이라고 한다.


3. 힙(Heap)의 활용

힙은 최댓값 혹은 최솟값을 빠르게 찾아내기에 유리한 자료구조이다.

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

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

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

  • 시뮬레이션 시스템

  • 네트워크 트래픽 제어

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

  • 수치 해석적인 계산


4. 힙(Heap)의 연산 및 시간복잡도

힙(Heap)의 연산 및 Big-O (Time Complexity)

  • 삽입 : 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올린다.
    완전 이진트리의 최대 높이는 O(logN)이고, 반복하는 최대 횟수도 O(logN)이 된다.
  • 삭제(추출) : 원소를 맨 위 넣어서 바닥까지 비교하면서 올린다.
    완전 이진트리의 최대높이는 O(logN)이고, 반복하는 최대횟수도 O(logN)이된다.

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

4-1 힙의 삽입과정 그림 설명

기본 배열

이번 예시에서는 위 7개의 숫자를 가지고 힙을 만드는 과정을 보일 것이다.

힙을 만들기 위해서는 값 삽입 -> 힙 구조로 변경 -> 값 삽입 -> 힙 구조로 변경 -> 계속 반복해주면 된다.

값을 넣을 때 힙 구조가 붕괴되는 경우가 있어 이 과정을 반복하는 것이다.

첫 번째 값(5) 삽입

우선 첫 번째 값부터 차례대로 트리에 넣어준다.

  • '5'를 트리에 넣었다.

두 번째 값(2) 삽입

이번에는 '2'를 넣었다.

부모 노드(5)가 자식 노드(2) 보다 크기 때문에 swap을 하지 않고 넘어간다.

세 번째 값(6) 삽입

부모 노드(5)가 자식 노드(6) 보다 작기 때문에 힙 구조가 붕괴되었다.

따라서 두 값을 swap 해주어야 한다.


swap을 하고 나면 위와 같은 트리 모양으로 바뀐다.

힙은 이렇게 항상 부모 노드가 자식 노드보다 커야 한다는 조건이 있다.

그래서 매번 값이 들어올 때마다 값을 비교하고 swap을 해줘야 한다.

자식 노드들 끼리는 값을 비교하지 않는다. 즉, 위 예시에서 2와 5는 비교하지 않는다는 것이다.

네 번째 값(1) 삽입

이번에는 '1'을 넣었다.

부모 노드(2)가 자식 노드(1)보다 크기 때문에 swap을 하지 않는다.

다섯 번째 값(3) 삽입

'3'을 넣었다.

부모 노드(2)가 자식 노드(3) 보다 작기 때문에 swap을 해줘야 한다.


swap을 하여 힙 구조로 변경하였다.

여섯 번째 값(4) 삽입

부모 노드(5)가 자식 노드(4) 보다 크기 때문에 swap을 하지 않는다.

일곱 번째 값(7) 삽입

부모 노드(5)가 자식 노드(7) 보다 작기 때문에 swap을 해준다.


이번엔 부모 노드(6)가 자식 노드(7) 보다 작기 때문에 또다시 swap을 해준다.

힙 구조 완성

이렇게 해서 힙 구조가 완성되었다.

완전 이진 트리이면서 부모 노드가 자식 노드보다 큰 트리 구조이다.

이러한 과정을 통해 '7'이라는 최댓값을 빠르게 찾을 수 있는 구조가 바로 힙 인 것이다.

완성된 힙 배열형태

완성된 힙 구조를 일렬로 나열하였다.

트리 모양으로 봤을 땐 뭔가 숫자들이 정렬되어 보였는데 막상 이렇게 보니 뒤죽박죽인 느낌이다.

힙 구조는 최댓값(혹은 최솟값)을 빨리 찾기 위한 구조이지 이걸 사용했다고 정렬이 되지는 않기 때문이다.


힙 구조를 만들기 위해서 힙 삽입 -> 힙 구조로 변경 -> 힙 삽입 -> 힙 구조로 변경을 반복했다면

정렬을 하기 위해서는 힙 삭제 -> 힙 구조로 변경 -> 힙 삭제 -> 힙 구조로 변경을 반복해야 한다.

이 과정을 통틀어 힙 정렬이라고 하며 이에 대해서는 다음 발표자의 내용이 정렬 이라서 그때 다루지 않을까 싶다.

5.자바스크립트 힙의 구현

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]를 자식의 오른쪽 노드로 지정해준다.
    1. 의 조건이 불충분하면 자식의 왼쪽 노드가 더 크다는 뜻이므로 현재 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;
      }
    }
  }

최종 구현 코드

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

결과 콘솔창

참고 및 출처

profile
Seong Hyeon Kim
삽질도 100번 하면 요령이 생긴다. 부족한 건 경험으로 채우는 백엔드 개발자
이전 포스트

[자료구조] - 스택(Stack)

다음 포스트

[24.01.18] Today CS 공부 [배열,링크드리스트]

0개의 댓글