힙(Heap) 이란?

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) (완전 이진 트리: 노트를 삽입할때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리)

힙을 사용하는 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
• 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, O(logn)이 걸림
• 우선순위 큐와 같이 최대값, 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

힙(Heap) 구조

힙은 최대값을 구하기 위한 구조(최대 힙, Max Heap)와, 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있음 힙의 조건

• 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)

  • 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
  • 결국 가장 위의 노드가 가장 큰(혹은 작은) 값이 된다 -> 최대값/최소값을 구하려면 루트 노드의 값만 가져오면 됨 -> 시간 절약!
• 완전 이진 트리 형태를 가짐

힙과 이진 탐색 트리(BST)의 공통점과 차이점

공통점 모두 이진 트리다 -> 자식 노드를 2개 이상 가지지 않는다. 차이점

• 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
• 이진 탐색 트리는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순으로 값이 커진다

• 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없다

  • 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도, 왼쪽이 클 수도 있음
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨

힙 동작

Max Heap을 기준으로 설명

힙에 데이터 삽입하기

기본 동작

힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입

삽입할 데이터가 힙의 데이터보다 클 경우

먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐 채워진 노드 위치에서 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함(swap)

데이터 삭제하기

• 보통 삭제는 최상단 노드(root 노드)를 삭제하는 것이 일반적임

  • (힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것이라서)
• 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동

• root 노드의 값이 child 노드보다 작을 경우, root 노드의 child 노드 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔줌 (swap)

  • 이후로 부모 노드가 child 노드보다 클 때까지 swap 반복

힙 구현

힙과 배열

일반적으로 힙 구현시 배열 자료구조를 활용함 (완전 이진 트리이기 때문에)

배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀 더 수월함

• 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
• 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 2
• 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

Max Heap 기준으로 구현

class Heap {
  heapArray;
  constructor(value) {
    this.heapArray = [null, value];
  }
  insert(value) {
    this.heapArray.push(value);

    this.swap(this.heapArray.length - 1);
  }
  swap(index) {
    const parentIndex = parseInt(index / 2);

    if (index <= 1) {
      return;
    }

    if (this.heapArray[index] <= this.heapArray[parentIndex]) {
      return;
    }

    const parentNodeValue = this.heapArray[parentIndex];
    this.heapArray[parentIndex] = this.heapArray[index];
    this.heapArray[index] = parentNodeValue;

    this.swap(parentIndex);
  }
}

const maxHeap = new Heap(15);

maxHeap.insert(10);
maxHeap.insert(8);
maxHeap.insert(5);
maxHeap.insert(4);
maxHeap.insert(20);
console.log(maxHeap.heapArray);