상위 질문
타임라인
채팅
관점

힙 알고리즘

위키백과, 무료 백과사전

Remove ads

힙(Heap)의 알고리즘은 n개체의 가능한 모든 순열을 생성한다. 1963년 힙(B.R. Heap)에 의해 처음 제안되었다.[1]이 알고리즘의 주요한 특징은 움직임을 최소화한다는 것이다. 단일 요소 쌍을 교환하여 이전 순열에서 각 순열을 생성함으로써 이러한 결과를 갖을수있다. 다른 n-2 요소는 방해받지 않는다. 순열 생성 알고리즘에 대한 1977년 검토에서 로버트 세지윅(Robert Sedgewick)은 당시 컴퓨터로 순열을 생성하는 데 가장 효과적인 알고리즘이라고 결론지은바있다.[2]

힙의 알고리즘에 의해 생성된 n개 객체의 순열 시퀀스는 n + 1 객체의 순열 시퀀스의 시작이다. 따라서 힙(Heap) 알고리즘(OEIS의 시퀀스 A280318)에 의해 생성된 무한 시퀀스의 순열이 계산된바 있다.

예

n(3)개의 원소를 갖는 집합에서의 순열의 경우의 수를 보여주는 힙 알고리즘을 사용한 자바스크립트 프로그램

<html>
<script>
function permute(permutation) {
 var length = permutation.length ;
 var    result =   permutation.slice()  ;
 var    c = new Array(length).fill(0) ;
  var   i = 1, k, p;
 while (i < length) {
   if (c[i] < i) {
     k =  i%2 && c[i];
     p = permutation[i];
     permutation[i] = permutation[k];
     permutation[k] = p;
     c[i]++;
     i = 1;
     result.push(  permutation.slice());
   } else {
     c[i] = 0;
     i++;
   }
 }
 return result;
}
window.onload = function () {
document.write(permute([1, 2, 3]));
}
</script>
</html>
결과 1,2,3, 2,1,3, 3,1,2, 1,3,2, 2,3,1, 3,2,1
Remove ads

힙정렬

힙(Heap)알고리즘은 힙정렬(heap sort)과 다르지만 다른 n-2 요소는 방해받지 않는다는 스왑 알고리즘(swap algorithm)을 보여준다는 점에서 비교할만한 유용한 유사한 점도 있다.

같이 보기

각주

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads