Skip to content

Latest commit

 

History

History
244 lines (187 loc) · 9.3 KB

힙.md

File metadata and controls

244 lines (187 loc) · 9.3 KB

힙(heap)

힙이란?

  • 힙(Heap)은 노드의 값이 그 자식 노드의 값보다 항상 크거나 같은 트리 구조를 말한다.(혹은 작거나 같다.) 이를 **힙 속성(heap property)**라고 한다.
  • 힙은 완전 이진 트리의 일종이다. 즉, 트리의 높이를 h(h>0)라 할 때, 모든 잎 노드들은 h 또는 h-1 레벨에 있어야 한다.
  • 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
  • 중복된 값은 허용한다. (이진 탐색 트리에서는 중복 값을 허용하지 않는다.)

우선순위 큐를 구현할 때 내부적으로 최소 힙 또는 최대 힙을 이용한다. 최소 힙을 이용하는 경우 '값이 낮은 데이터가 먼저 삭제'되며, 최대 힙을 이용하는 경우 '값이 큰 데이터가 먼저 삭제'된다. 이때 힙은 삽입과 삭제에 O(NlogN)의 시간 복잡도를 가진다.

힙(heap)의 종류

  • 최대 힙(max heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
    • key(부모 노드) >= key(자식 노드)
  • 최소 힙(min heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
    • key(부모 노드) <= key(자식 노드)

image

힙 구현

힙의 부모와 자식 간에 다음과 같은 관계가 성립한다.

  • 왼쪽 자식의 index = 부모의 index * 2 + 1
  • 오른쪽 자식의 index = (부모의 index * 2) + 2
  • 부모의 index = Math.floor((자식의 index - 1) / 2)
class MinHeap {
  constructor() {
    // 힙을 저장할 배열
    this.heap = [];
  }

  // 힙의 크기를 반환하는 메서드
  size() {
    return this.heap.length;
  }

  // 두 값을 바꿔주는 메서드
  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }
}

삽입 연산

Min Heap의 삽입 연산은 다음과 같은 단계로 이루어진다.

  1. Heap의 마지막 위치에 요소를 추가한다.
  2. 새로운 요소를 추가한 위치에서부터, 부모 노드와 새로 추가된 노드의 값을 비교한다. 만약 새로 추가된 노드의 값이 부모 노드의 값보다 작다면, 부모 노드와 새로 추가된 노드의 위치를 교환한다.
  3. 이전 단계에서 교환된 새로 추가된 노드와 부모 노드의 값 비교를 반복한다. 이 단계를 반복하여 Min Heap의 규칙을 지키도록 한다.

  1. 먼저 힙의 마지막 노드로 새로운 요소 2를 삽입한다. image

  2. 부모 노드 6과 비교했을 때 2가 작으므로 교체한다.

image

  1. 부모 노드 3과 비교했을 때 2가 작으므로 교체한다.

image

  1. 부모 노드 1과 비교했을 때 2가 크므로 더 이상 교체하지 않는다.

코드로 구현한 것은 다음과 같다.

// 새로운 노드를 추가하는 메서드
add(value) {
  this.heap.push(value); // 힙의 끝에 새로운 노드 추가
  this.bubbleUp(); // 새로운 값이 추가된 위치에서 bubbleUp() 수행
}

bubbleUp() {
  let index = this.heap.length - 1; // 새로운 노드가 추가된 위치
  let parentIdx = Math.floor((index - 1) / 2); // 부모 노드의 위치
  while (
    this.heap[parentIdx] && // 부모 노드가 존재하고
    this.heap[index][1] < this.heap[parentIdx][1] // 새로운 노드가 부모 노드보다 작은 경우
  ) {
    this.swap(index, parentIdx); // 두 노드의 값을 교체
    index = parentIdx; // 인덱스를 부모 노드의 인덱스로 변경
    parentIdx = Math.floor((index - 1) / 2); // 새로운 부모 노드의 인덱스 계산
  }
}

bubbleUp

힙에 값을 삽입할 때 부모와 비교해서 값이 크거나 작으면(최소 힙의 경우 부모가 자신보다 크면, 최대 힙의 경우 부모가 자신보다 작으면) 부모와 값을 교환해서 올바르게 정렬이 될 때 까지 올라가는 것을 bubbleUp이라 한다.

삭제 연산

Min Heap의 삭제 연산은 다음과 같은 단계로 이루어진다.

  1. Heap에서 가장 작은 값을 가진 노드(루트 노드)를 제거한다. 이때, Min Heap에서 가장 작은 값은 루트 노드이다.
  2. Heap의 맨 마지막에 있는 노드를 새로운 루트 노드로 이동시킨다.
  3. 새로운 루트 노드와 자식 노드의 값을 비교하여, 자식 노드의 값이 작다면 루트 노드의 위치를 교환한다.
  4. 이전 단계에서 교환된 새로운 루트 노드와 자식 노드의 값 비교를 반복한다. 이 단계를 반복하여 Min Heap의 규칙을 지키도록 한다.

  1. 먼저 루트 노드가 삭제된다. 빈 루트 노드 자리에는 힙의 마지막 노드 7을 가져온다.

image

  1. 새로운 루트 노드인 7과 자식 노드들을 비교했을 때 7이 더 크므로 교체되어야 한다. 이때 자식 노드 중 더 작은 값인 3과 7이 교체된다.

image

  1. 7이 아직 자식 노드들보다 더 크기 때문에 교체되어야 한다. 이때 자식 노드 중 더 작은 값인 5와 7이 교체된다.

image

  1. 7이 자식 노드들보다 작으므로 더 이상 교체하지 않는다.

코드로 구현한 것은 다음과 같다.

poll() {
  if (this.heap.length === 1) {
    return this.heap.pop();// 힙의 크기가 1인 경우, 힙에서 값을 삭제하고 return
  }
  const value = this.heap[0];// 힙의 최소값(루트 노드의 값)을 저장
  this.heap[0] = this.heap.pop();// 힙의 끝에 있는 값을 루트 노드로 이동
  this.bubbleDown();// 루트 노드에서 bubbleDown을 수행
  return value;// 삭제한 최소값 return
}
bubbleDown() {
  let index = 0;// 루트 노드의 index
  let leftIdx = index * 2 + 1;// 왼쪽 자식 노드의 index
  let rightIdx = index * 2 + 2;// 오른쪽 자식 노드의 index
  while (
// 왼쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작거나
    (this.heap[leftIdx] && this.heap[leftIdx][1] < this.heap[index][1]) ||
// 오른쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작은 경우
    (this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[index][1])
  ) {
    let smallerIdx = leftIdx;// 왼쪽 자식 노드가 더 작다고 가정
    if (
      this.heap[rightIdx] &&
      this.heap[rightIdx][1] < this.heap[smallerIdx][1]// 오른쪽 자식 노드가 더 작다면
    ) {
      smallerIdx = rightIdx;// 오른쪽 자식 노드의 index로 변경
    }
    this.swap(index, smallerIdx);// 두 노드의 값을 교체
    index = smallerIdx;// index를 더 작은 값의 자식 노드의 index로 변경
    leftIdx = index * 2 + 1;// 왼쪽 자식 노드의 index 계산
    rightIdx = index * 2 + 2;// 오른쪽 자식 노드의 index 계산
  }
}

bubbleDown

루트 노드를 삭제하고 마지막 노드를 루트로 올리고 루트 노드와 아래 자식 노드들과 비교해서 값이 크거나 작으면(최소 힙의 경우 자식이 자신보다 값이 작으면, 최대 힙의 경우 자식이 자신보다 값이 크면) 자식과 값을 교환해서 올바르게 정렬이 될 때 까지 내려가는 것을 bubbleDown이라 한다.

전체 코드

주석을 제거한 전체 코드는 다음과 같다.

class MinHeap {
  constructor() {
    this.heap = [];
  }
  size() {
    return this.heap.length;
  }
  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }
  add(value) {
    this.heap.push(value);
    this.bubbleUp();
  }
  poll() {
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const value = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return value;
  }
  bubbleUp() {
    let index = this.heap.length - 1;
    let parentIdx = Math.floor((index - 1) / 2);
    while (
      this.heap[parentIdx] &&
      this.heap[index][1] < this.heap[parentIdx][1]
    ) {
      this.swap(index, parentIdx);
      index = parentIdx;
      parentIdx = Math.floor((index - 1) / 2);
    }
  }
  bubbleDown() {
    let index = 0;
    let leftIdx = index * 2 + 1;
    let rightIdx = index * 2 + 2;
    while (
      (this.heap[leftIdx] && this.heap[leftIdx][1] < this.heap[index][1]) ||
      (this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[index][1])
    ) {
      let smallerIdx = leftIdx;
      if (
        this.heap[rightIdx] &&
        this.heap[rightIdx][1] < this.heap[smallerIdx][1]
      ) {
        smallerIdx = rightIdx;
      }
      this.swap(index, smallerIdx);
      index = smallerIdx;
      leftIdx = index * 2 + 1;
      rightIdx = index * 2 + 2;
    }
  }
}

참고