JavaScript 힙(Heap)

김민기·2022년 3월 27일
0

Programmers_Study

목록 보기
8/9
post-thumbnail

힙(Heap)

  힙을 사용하기 전에 우선순위 큐에대해서 알고 있어야 한다. 우선순위 큐는 일반적인 큐와 달리 요소마다 우선순위를 갖고 있으며, FIFO 구조에 따라 가장 첫 번째 요소가 먼저 출력되는 것이 아니라 우선순위가 높은 요소가 먼저 출력된다.

우선순위 큐는 자료구조가 아닌 개념이다.

  힙은 이진 트리 형태를 가지며 요소가 삽입 또는 삭제 될때마다 우선 순위가 가장 높은(또는 낮은) 요소를 찾기 위해 정렬되는 특징이 있다.

자바스크립트에서 힙 구현하기

  우선순위가 가장 높은 요소를 루트 노드로 사용하는 최대 힙(Max Heap)과 우선순위가 가장 낮은 요소를 루트 노드로 사용하는 최소 힙(Min Heap)이 있다.

//Max Heap
class MaxHeap {
  constructor() {
    this.heap = [null];
  }
}

 배열로 구현할 것이기 때문에 연결리스트 처럼 다음 노드를 가리키는 포인터가 필요 없다. 다만 배열의 인덱스는 0부터 시작하기 때문에 1로 맞춰주기 위해서 가장 첫 번째 배열은 null로 초기화하고 사용하지 않는다.

MaxHeap.prototype.push = function(value) {
  this.heap.push(value);
  
  let currentIndex = this.heap.length - 1;
  let parentIndex = Math.floor(currentIndex / 2);
  
  while(parentIndex !== 0 && this.heap[parentIndex] < value) {
    const temp = this.heap[parentIndex];
    this.heap[parentIndex] = value;
    this.heap[currentIndex] = temp;
    
    currentIndex = parentIndex;
    parentIndex = Math.floor(currentIndex / 2);
  }
};

 우선 heap에 새로운 값을 추가한다. 따라서 heap의 길이는 1 증가한 상태이다. currentIndex는 추가한 요소의 인덱스를 의미하고 parentIndex는 추가한 요소의 부모 요소를 가리킨다.

 부모 인덱스의 값이 0이 아니고(루트 요소가 아니다.) 추가한 요소의 값이 부모 인덱스의 값보다 클 경우 부모 인덱스와 위치를 바꾼다. 그리고 나서 부모 인덱스가 현재 인덱스가 되어서 루트 요소까지 반복해서 값을 변경한다.

MaxHeap.prototype.pop = function() {
  const returnValue = this.heap[1];
  this.heap[1] = this.heap.pop();
  
  let currentIndex = 1;
  let leftIndex = 2;
  let rightIndex = 3;
  
  while(
    this.heap[currentIndex] < this.heap[leftIndex] ||
    this.heap[currentIndex] < this.heap[rightIndex]
  ) {
    const direction =
      this.heap[leftIndex] > this.heap[rightIndex] ? leftIndex : rightIndex;
    const temp = this.heap[currentIndex];
    this.heap[currentIndex] = this.heap[direction];
    this.heap[direction] = temp;
    
    currentIndex = direction;
    leftIndex = currentIndex * 2;
    rightIndex = leftIndex + 1;
  }
  return returnValue;
}

const maxHeap = new MaxHeap();
maxHeap.push(24);
maxHeap.push(36);
maxHeap.push(48);
maxHeap.push(54);
maxHeap.push(27);
maxHeap.push(39);
maxHeap.push(55);

console.log(maxHeap.pop());
console.log(maxHeap.pop());
console.log(maxHeap.pop());
console.log(maxHeap.pop());
console.log(maxHeap.pop());
console.log(maxHeap.pop());
console.log(maxHeap.pop());

출력 : 55 -> 54 -> 48 -> 39 -> 36 -> 27 -> 24
입력한 순서와 관계 없이 가장 큰 수부터 pop이 되는 것을 확인 할 수 있다. pop 함수의 동작은 root 요소의 값을 반환하는 것임으로 returnValue 변수를 만들어서 루트 요소의 값을 저장한다.(this.heap[1]) 그리고 heap의 마지막 요소를 첫 번째 요소로 가져온다. 가져온 요소보다 왼쪽 또는 오른쪽에 있는 요소가 더 클 경우 어느쪽 방향이 더 큰값인지 확인한 후 더 큰 방향으로 요소를 바꿔나간다.

방향을 정하지 않고 실행할 경우 어느정도 정렬이 되어있는 배열이라면 문제가 없겠지만 예시 처럼 순서 없이 요소를 추가할 경우 조건문에서 왼쪽 방향을 먼저하는가 오른쪽 방향을 먼저하는가에 따라 출력이 정상적으로 이뤄지지 않을 수 있다. 따라서 방향 조건도 잊지말고 확인해야 한다.

//MinHeap
class MinHeap {
  constructor() {
    this.heap = [null];
  }
}

MinHeap.prototype.push = function (value) {
  this.heap.push(value);
  let currentIndex = this.heap.length - 1;
  let parentIndex = Math.floor(currentIndex / 2);

  while (parentIndex !== 0 && this.heap[parentIndex] > value) {
    const temp = this.heap[parentIndex];
    this.heap[parentIndex] = this.heap[currentIndex];
    this.heap[currentIndex] = temp;

    currentIndex = parentIndex;
    parentIndex = Math.floor(currentIndex / 2);
  }
};

MinHeap.prototype.pop = function () {
  const returnValue = this.heap[1];
  this.heap[1] = this.heap.pop();

  let currentIndex = 1;
  let leftIndex = 2;
  let rightIndex = 3;

  while (
    this.heap[currentIndex] > this.heap[leftIndex] ||
    this.heap[currentIndex] > this.heap[rightIndex]
  ) {
    const direction =
      this.heap[leftIndex] > this.heap[rightIndex] ? rightIndex : leftIndex;

    const temp = this.heap[currentIndex];
    this.heap[currentIndex] = this.heap[direction];
    this.heap[direction] = temp;

    currentIndex = direction;
    leftIndex = currentIndex * 2;
    rightIndex = leftIndex + 1;
  }
  return returnValue;
};

const minHeap = new MinHeap();
minHeap.push(24);
minHeap.push(13);
minHeap.push(18);
minHeap.push(7);
minHeap.push(6);
minHeap.push(14);
minHeap.push(1);

console.log(minHeap.pop());
console.log(minHeap.pop());
console.log(minHeap.pop());
console.log(minHeap.pop());
console.log(minHeap.pop());
console.log(minHeap.pop());
console.log(minHeap.pop());

0개의 댓글