이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌14 - Algorithm - 일 년 전 등록 / 5달 전 수정

자료구조(힙, Heap), 힙 정렬, Heap sort

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요. 이번 시간에는 힙 정렬 대해 알아보겠습니다. 이 녀석은 트리이면서 배열인 이상한 놈입니다.

힙은 트리의 일종이지만 조금 특이한 성질을 가지고 있습니다. 힙에는 최대힙과 최소힙이 있는데, 일단 최대힙의 정의는 다음과 같습니다. 

완전 트리이면서 Root가 모든 경우에 자식들보다 커야한다.

최소힙은 Root가 자식보다 작으면 됩니다. 완전 트리란 무엇일까요? 바로 노드가 순서대로 들어있는 트리가 완전 트리입니다. 왼쪽에서부터 차곡차곡 들어가는 트리죠. 한 줄이 다 찼으면 다음 줄 왼쪽에 노드가 들어가고요. 

undefined

Root가 자식보다 커야한다는 뜻은 다음과 같은 트리를 의미합니다. 트리 안의 서브트리에도 이 규칙이 적용됩니다. 또한 완전 트리이기 때문에 지난 시간처럼 트리로 만들지 않고 배열로 만들어도 됩니다. 다음 트리와 다음 배열은 같은 겁니다.

undefined

힙은 제거할 때 가장 위의 루트값이 빠집니다. 루트 값은 최대힙이면 숫자 중에 가장 큰 값, 최소힙이면 가장 작은 값이겠죠?

힙 정렬

위와 같은 힙의 성질을 이용해 힙 정렬을 할 수 있습니다. 랜덤한 순서의 숫자들을 힙으로 만들어 넣고, 힙에서 하나씩 제거하면 되죠. 가장 큰 값 또는 가장 작은 값 순서로 빠지기 때문에 알아서 정렬이 됩니다.

시간 복잡도는 데이터를 넣을 때도 O(lgN)이고 뺄 때도 O(lgN)이라 고른 성능을 보입니다. N개의 데이터를 모두 빼면 정렬이 되기 때문에 힙 정렬의 시간 복잡도는 O(NlgN)이 됩니다.

코드로 직접 만들어봅시다.

var Heap = (function() {
  function Heap() {
     this.arr = [];
  }
 function reheapUp(self, idx) {
    if (idx) {
      var parent = parseInt((idx - 1) / 2);
      if (self.arr[idx] > self.arr[parent]) {
        var temp = self.arr[idx];
        self.arr[idx] = self.arr[parent];
        self.arr[parent] = temp;
        reheapUp(self, parent);
      }
    }
  }
 function reheapDown(self, idx) {
    var left = 0;
    var right = 0;
    var large;
    if (idx * 2 + 1 < self.arr.length) {
      left = self.arr[idx * 2 + 1];
      if (idx * 2 + 2 < self.arr.length - 1) {
        right = self.arr[idx * 2 + 2];
      }
      if (left > right) {
        large = idx * 2 + 1;
      } else {
        large = idx * 2 + 2;
      }
      if (self.arr[idx] < self.arr[large]) {
        var temp = self.arr[idx];
        self.arr[idx] = self.arr[large];
        self.arr[large] = temp;
        reheapDown(self, large);
      }
    }
  }
  Heap.prototype.insert = function(number) {
    var last = this.arr.length;
    this.arr[last] = number;
    reheapUp(this, last);
    return true;
  };
  Heap.prototype.delete = function() {
    if (this.arr.length === 0) {
      return false;
    }
    var del = this.arr[0];
    this.arr[0] = this.arr.pop();
    reheapDown(this, 0);
    return del;
  };
  Heap.prototype.sort = function() {
    var sort = [];
    var count = this.arr.length;
    for (var i = 0; i < count; i++) {
      sort.push(this.delete());
    }
    return sort;
  };
  return Heap;
})();
var heap = new Heap();
heap.insert(5);
heap.insert(3);
heap.insert(7);
heap.insert(4);
heap.insert(2);
heap.insert(6);
heap.insert(1);
heap.sort(); // [7,6,5,4,3,2,1]

특이한 점은 reheapUp과 reheapDown이라는 내부적으로 힙의 순서를 재귀적으로 조정하는 함수가 있다는 겁니다. 힙은 트리를 배열로 표현한 것이기 때문에 트리 구조를 유지하려면 추가적인 과정 필요합니다. 

reheapUp은 배열 끝에 새로운 값을 받고, 그 값을 자신의 부모 노드(parseInt((idx - 1) / 2))와 비교해서 크면 서로 위치를 바꿉니다. 이를 재귀적으로 하면 됩니다. reheapDown은 배열 처음 값을 자기 왼쪽 자식(idx * 2 + 1), 오른쪽 자식(idx * 2 + 2) 둘 중에 큰 값과 비교해서 작으면 자리를 재귀적으로 바꿔줍니다.

sort 메소드를 호출할 시 내부적으로 delete를 this.arr의 개수만큼 호출합니다. 힙 정렬의 원리이죠? 최대값부터 빠지니까요. delete 메소드는 제일 첫 배열 값(빠지는 값)에 가장 마지막 배열 값을 넣고 reheapDown을 실행합니다.

힙은 정렬을 할 때 외에도 우선순위 큐를 만들 때에도 사용됩니다. 앞에서부터 요소가 빠지는 큐의 성질을 가지고 있고 항상 큰 값이 먼저 빠지기 때문입니다.

다음 시간에는 그래프에 대해 알아보겠습니다.

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

아직 댓글이 없습니다.