[ Javascript ] 힙정렬과 힙

힙이란?

힙은 이진트리구조이다.

최대힙과 최소힙이 있으며 자식노드로 올수록 커지면 최소힙, 작아지면 최대힙이라 할 수 있겠다.

 

최소힙기준으로 설명을 하자면

양 자식노드의 값은 루트노드보다 작아야한다. 

 

힙 구현

힙은 배열형태로 구현할 수 있다.

부모노드 인덱스 * 2가 왼쪽자식, 부모노드 인덱스*2+1이 오른쪽 자식 되시겠다.

삽입

힙의 삽입은 배열로 구현할 경우, 배열의 마지막 인덱스에 요소를 추가하는 것으로 시작된다.

그리고 해당 인덱스와 부모노드를 인덱스값이 작을떄까지(클때까지) 비교하며 둘의 위치를 조정한다.

루트까지 진행한다.

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

    while (
      this.heap[parentIndex] &&
      this.heap[parentIndex] > this.heap[currentIndex]
    ) {
      this.swap(parentIndex, currentIndex);
      currentIndex = parentIndex;
      parentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }

이진트리의 특성상 삽입은 O(logN)의 시간복잡도를 갖는다.

삭제(pop)

삭제는 해당 노드를 삭제한 후, 자식노드가 있다면 자식 노드들 중 작은값(큰값)을 가져온다.

변경한 후 heap조건에 맞는지 확인한다.

나는 pop형태로 구현하여 root값을 삭제하고 반환하도록 구현했다.

  pop() {
    const [root] = this.heap;
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    let currentIndex = 0;
    let leftIndex = 1;
    let rightIndex = 2;
    while (
      (this.heap[leftIndex] &&
        this.heap[leftIndex] < this.heap[currentIndex]) ||
      (this.heap[rightIndex] && this.heap[rightIndex] < this.heap[currentIndex])
    ) {
      if (this.heap[leftIndex] && this.heap[rightIndex]) {
        const smaller = this.getSmaller(this.heap, leftIndex, rightIndex);
        this.swap(smaller, currentIndex);
        currentIndex = smaller;
      } else if (this.heap[leftIndex]) {
        this.swap(leftIndex, currentIndex);
        currentIndex = leftIndex;
      } else {
        this.swap(rightIndex, currentIndex);
        currentIndex = rightIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
    return root;
  }

이진트리의 특성상 삭제도 O(logN)의 시간복잡도를 갖는다.

구현

이렇게 만들어진 힙에 정렬이 필요한 배열의 요소를 모두 넣고, 힙이 빌때까지 pop해주면 정렬된 결과가 나오게 된다.

Heap.js

class Heap {
  constructor() {
    this.heap = [];
  }
  isEmpty() {
    return this.heap.length === 0;
  }
  getSmaller(arr, i, j) {
    if (arr[i] < arr[j]) {
      return i;
    } else {
      return j;
    }
  }
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [
      this.heap[index2],
      this.heap[index1],
    ];
  }
  add(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor((currentIndex - 1) / 2);

    while (
      this.heap[parentIndex] &&
      this.heap[parentIndex] > this.heap[currentIndex]
    ) {
      this.swap(parentIndex, currentIndex);
      currentIndex = parentIndex;
      parentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }
  pop() {
    const [root] = this.heap;
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    let currentIndex = 0;
    let leftIndex = 1;
    let rightIndex = 2;
    while (
      (this.heap[leftIndex] &&
        this.heap[leftIndex] < this.heap[currentIndex]) ||
      (this.heap[rightIndex] && this.heap[rightIndex] < this.heap[currentIndex])
    ) {
      if (this.heap[leftIndex] && this.heap[rightIndex]) {
        const smaller = this.getSmaller(this.heap, leftIndex, rightIndex);
        this.swap(smaller, currentIndex);
        currentIndex = smaller;
      } else if (this.heap[leftIndex]) {
        this.swap(leftIndex, currentIndex);
        currentIndex = leftIndex;
      } else {
        this.swap(rightIndex, currentIndex);
        currentIndex = rightIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
    return root;
  }
}
module.exports = Heap;

heapSort.js

const Heap = require('../dataStructure/heap/Heap.js');
const heapSort = (inputValue) => {
  const heap = new Heap();
  inputValue.forEach((number) => {
    heap.add(number);
  });
  const result = [];
  while (!heap.isEmpty()) {
    result.push(heap.pop());
  }
  return result;
};
module.exports = heapSort;

테스트 코드

const 버블정렬 = require('../sort/bubbleSort');
const 힙정렬 = require('../sort/heapSort');
const 삽입정렬 = require('../sort/insertSort');
const 합병정렬 = require('../sort/mergeSort');
const 퀵정렬 = require('../sort/quickSort');
const 선택정렬 = require('../sort/selectionSort');
const testData = [
  {
    testInput: [5, 3, 1],

    testAnswer: [1, 3, 5],
  },
  {
    testInput: [5, 3, 1, 5, 3, 22],
    testAnswer: [1, 3, 3, 5, 5, 22],
  },
  {
    testInput: [5, 3, 100, 1, 5, 99, 3, 22],
    testAnswer: [1, 3, 3, 5, 5, 22, 99, 100],
  },
  {
    testInput: [8, 9, 8, 8, 9, 8, 9],
    testAnswer: [8, 8, 8, 8, 9, 9, 9],
  },
  {
    testInput: [1, 9, 7, 8, 6, 8, 9],
    testAnswer: [1, 6, 7, 8, 8, 9, 9],
  },
];

const testFunction = [
  선택정렬,
  삽입정렬,
  버블정렬,
  합병정렬,
  퀵정렬,
  힙정렬,
];
testFunction.forEach((func) => {
  testData.forEach((testData, index) => {
    test(`${func.name} 테스트 ${index}`, () => {
      expect(func(testData.testInput)).toEqual(testData.testAnswer);
    });
  });
});