Javascript로 Heap을 구현해보자

힙이란?

완전 이진 트리의 일종
정렬, 우선순위 큐, 스케쥴링 등 다양한 알고리즘에 사용된다.

용어 정리

부모 노드	자식 노드	루트 노드	리프 노드	레벨	높이
특정 노드의 상위	특정 노으의 하위	트리의 최상단	트리의 말단	루트 ~ 리프 트리의 깊이 0부터 시작	리프 ~ 루트 트리의 높이 1부터 시작

 

종류

최대 힙

부모 노드의 값 >= 자식 노드의 값
항상 부모 노드의 값이 자식 노드의 값보다 크거나 같음

최소 힙

부모 노드의 값 <= 자식 노드의 값
항상 부모 노드의 값이 자식 노드의 값보다 작거나 같음

활용 예시

삽입/삭제 정렬 시간복잡도

	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
힙	O(logn)	O(logn)

우선순위 큐

배열, 연결리스트, 힙으로 구현하능하지만 힙이 가장 효율적이다.

최단 경로 알고리즘

우선 순위가 높은 기준으로 노드를 선택해 목표 노드까지 최단 경로를 구한다.

힙정렬

최대값 또는 최소값을 구하는 데 효율적이다. 다만 특정 값의 위치를 구하기에는 모든 노드를 방문해야 할 수 있기 때문에 비효율적이다.

 

구현 방법

기본 아이디어

위의 그림을 통해 알 수 있는 정보

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

또한, 힙은 정렬하기 위해서 자신의 부모 또는 자식노드와 값을 비교한 다음 자리를 교환하는 방식을 사용한다.

따라서

• 배열 생성
  • 이때 편의를 위해 인덱스 0은 비워두고 1부터 요소를 삽입한다.
• 새로운 요소가 생기면 가장 마지막 노드 뒤에 추가 (push)
• 해당 요소를 부모 노드와 비교하며 위치 바꾸기 (swap)

class MaxHeap {
  constructor() {
    // 힙을 저장할 배열
    this.heap = [null];
  }

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

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

삽입

• 노드 삽입

• 부모 노드와 비교 후 자리 교환

• 교환 중단

코드

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

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

삭제

• 루트 노드 제거

• 배열 마지막 노드 루트로 올리기

• 자식 노드와 비교하며 교환

• 교환 중단

코드

pop() {
  if (this.heap.length === 2) {
    return this.heap.pop(); // 힙의 크기가 1인 경우, 힙에서 값을 삭제하고 return
  }

  const value = this.heap[1]; // 힙의 최소값(루트 노드의 값)을 저장
  this.heap[1] = this.heap.pop(); // 힙의 끝에 있는 값을 루트 노드로 이동
  this.bubbleDown(); // 루트 노드에서 bubbleDown을 수행
  return value; // 삭제한 최소값 return
}

bubbleDown() {
  let index = 1; // 루트 노드의 index
  let leftIdx = index * 2; // 왼쪽 자식 노드의 index
  let rightIdx = index * 2 + 1; // 오른쪽 자식 노드의 index

  while (
    // 왼쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작거나
    (this.heap[leftIdx] && this.heap[leftIdx] > this.heap[index]) ||
    // 오른쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작은 경우
    (this.heap[rightIdx] && this.heap[rightIdx] > this.heap[index])
  ) {
    let smallerIdx = leftIdx; // 왼쪽 자식 노드가 더 작다고 가정
    if (
      this.heap[rightIdx] &&
      this.heap[rightIdx] < this.heap[smallerIdx] // 오른쪽 자식 노드가 더 작다면
    ) {
      smallerIdx = rightIdx; // 오른쪽 자식 노드의 index로 변경
    }

    this.swap(index, smallerIdx); // 두 노드의 값을 교체
    index = smallerIdx; // index를 더 작은 값의 자식 노드의 index로 변경
    leftIdx = index * 2; // 왼쪽 자식 노드의 index 계산
    rightIdx = index * 2 + 1; // 오른쪽 자식 노드의 index 계산
  }
}

전체 코드

class MaxHeap {
  constructor() {
    this.heap = [0];
  }

  size() {
    return this.heap.length - 1;
  }

  swap(idx1, idx2) {
      [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }

  push(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  pop() {
    if (this.heap.length === 2) {
      return this.heap.pop();
    }

    const value = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.bubbleDown();
    return value;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    let parentIdx = Math.floor(index / 2);
    while (
      this.heap[parentIdx] &&
      this.heap[index] > this.heap[parentIdx]
    ) {
      this.swap(index, parentIdx);
      index = parentIdx;
      parentIdx = Math.floor(index / 2);
    }
  }

  bubbleDown() {
    let index = 1;
    let leftIdx = index * 2;
    let rightIdx = index * 2 + 1;

    while (
      (this.heap[leftIdx] && this.heap[leftIdx] > this.heap[index]) ||
      (this.heap[rightIdx] && this.heap[rightIdx] > this.heap[index])
    ) {
      let smallerIdx = leftIdx;
      if (
        this.heap[rightIdx] &&
        this.heap[rightIdx] > this.heap[smallerIdx]
      ) {
        smallerIdx = rightIdx;
      }

      this.swap(index, smallerIdx);
      index = smallerIdx;
      leftIdx = index * 2;
      rightIdx = index * 2 + 1;
    }
  }
}