Heap

최소 힙

 

  HeapSort란 최대 힙 트리나 최소 힙 트리를 만들어 정렬하는 방법이다. 최대 힙은 루트가 트리의 값들 중 가장 큰 값을 갖고, 최소 힙은 루트가 가장 작은 값을 갖는다. 위의 트리는 [0, 2, 1, 5, 3, 4, 8] 이라는 배열과 동일하다.

 

 

1. 요소를 추가할 때

  새로운 요소가 추가되면 우선 가장 트리의 가장 마지막으로 넣어진다. 그 후 부모노드와 비교해서 작으면 부모와 위치를 교환하고, 이를 반복해나간다.

  노드의 자식은 2개까지 가질 수 있다. 따라서 n번째 노드의 부모는 Math.floor((n-1) / 2) 와 동일하다. 예를 들어 배열 인덱스가 0부터 시작하고 값이 [0, 1, 2]일 때 최상위 노드는 0이며, 자식으로 1과 2를 갖는다. 0 = f(1) = f(2) 를 만족시켜야 하므로 f(n) = Math.floor((n-1)/2) 이다.

 

function swap(idx1, idx2, arr) { //두 값을 교환
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

function getParentIdx(idx) { //배열은 0부터 시작
  return Math.floor((idx - 1) / 2);
}

function insert(heap, item) {
  //1. 일단 넣고 부모 index를 계산한다.
  let idx = heap.length;
  let parentIdx = getParentIdx(idx);
  heap.push(item);

  //2. 부모와 비교해서 작으면 부모와 교환하는 것을 반복한다.
  while (item < heap[parentIdx]) {
    swap(idx, parentIdx, heap);
    idx = parentIdx;
    parentIdx = getParentIdx(idx);
  }
  return heap;
}

  코드로 구현하면 위와 같다. insert()구현 전에 heap의 두 노드의 값을 교환하는 swap()과 부모노드의 인덱스를 계산하는 getParentIdx를 구현하여주었다. 그 후 Insert는 쉽게 구현할 수 있다.

 

 

 

2. 요소를 제거할 때

  루트노드를 제거한 경우 우선 가장 마지막 노드의 값이 루트노드의 값으로 변경된다. 그 후 자식 중 더 작은 값과 계속 비교해서 해당 값이 더 크다면 자식요소와 교환하고 이를 반복해나간다. 자식 노드는 부모노드와 반대로 n*2 + 1로 구하며, 두 자식 노드 중 더 작은 노드와 값을 비교하고 교환해나간다.

 

 function getLeftChildIdx (idx){
    return idx * 2 + 1;
  }
  
function removeRoot(heap) {
  //1. 가장 끝에있는 요소가 루트로 간다.
  swap(0, heap.length - 1, heap);
  heap.pop();

  if (heap.length === 0)
    return [];

  let idx = 0;
  let leftIdx = getLeftChildIdx(idx);
  let rightIdx = leftIdx + 1;

  //2. 자식 둘 중에 더 작은 값이랑 계속 비교해나간다.
  while (heap[idx] > heap[leftIdx] || heap[idx] > heap[rightIdx]) {
    let childIdx = heap[leftIdx] > heap[rightIdx] ? rightIdx : leftIdx;
    swap(idx, childIdx, heap);
    idx = childIdx;
    leftIdx = getLeftChildIdx(idx);
    rightIdx = leftIdx + 1;
  }
  return heap;
}

 

 

3. 힙정렬

const binaryHeap = function (arr) {
  return arr.reduce((heap, item) => {
    return insert(heap, item);
  }, []);
};

const heapSort = function (arr) {
  let minHeap = binaryHeap(arr);
  const sorted = [];
  while (minHeap.length > 0) {
    sorted.push(minHeap[0]);
    minHeap = removeRoot(minHeap);
  }
  return sorted;
};

  힙정렬은 최소 힙을 이용한 정렬이다. 최소 힙의 루트 노드는 가장 작은 수이다. 따라서 배열을 정렬하기 위해 먼저 계속 배열의 요소들을 insert해나가 최소 힙을 만든 후에 최소 힙의 루트 노드를 계속 pop하면 오름차순으로 정렬된 배열을 얻을 수 있다.

 

  Heap은 우선순위가 있는 데이터를 다룰 때 유리하다. 야근지수(Programmers)와 같은 문제에서 이를 활용할 수 있다.

 

---

gif의 프로그램 출처: www.cs.usfca.edu/~galles/visualization/Heap.html

Heap Visualization