heap

나열식 2진트리.
최소값 기준이나 최대값 기준을 다량으로 빠르게 뽑아내는 알고리즘에 이용된다.

동의어 : 힙
관련 : heap sort
추가서술 : 힙 구축, 힙 값 추출

...

// 힙 구축

힙 구축(initialize ...?)은 최하단에서부터 시작, 상단으로 옮겨가면서 힙구축을 마친다.

상단값보다 하단값이 올라오는 게 맞는 경우,
하단값과 상단값의 상하교환이 이루어지지만,

만약(?), 상단값과 교환을 두번했다고 한다면, (하단 값은 두개가 보통이다.)
기존에 구축(?)하던 힙의 체계(system...?)가 무너질 수 있으므로

하단 값을 먼저 비교해서 상단값과 비교할 값을 선택한다.

...

배열은 a[], 최초 위치값은 1, 힙의 크기가 L 일 때 ( => 배열의 최종값=a[L] )
비교함수는 isrightLess(a, b) 이라 정의해두고 ( a<0 => 0, a>=b => 1 )
정수부분 추출함수를 parseInt() (javascript), 루프함수는 for(){ } while() { } ,
루프용 변수 i, k, 임시용 변수 up, sv

for (i=parseInt(L/2); i>1; i-=2) {
  k=i; if (k+1<=L)  if (isrightLess(a[k], a[k+1])) k++; // k=k+1;
  while (k<=L) {
    up=parseInt(k/2);
    if (isrightLess(a[k], a[up])) break;
    sv=a[k]; a[k]=a[up]; a[up]=sv;

    k=k*2;
    }
  }

*참고* 잘 정의된 heap 구축식에서는
sv 값을 미리 지정해서 비교문 종료 후에 sv 값을 넘기지만, (버블소트처럼...?)
= =;... 손에(?) 안익어서 그냥 swap 형식을 취했다.

...

// 힙 값 추출

구축된 힙의 최상단 값을 뽑아내면 최상단 값이 비워졌다고 판단할 수 있으므로
그 상황(?)을 복구(?)하기 위해 값 추출 후 최종값을 최상단에 당겨와서 다시 힙구축을 해야(?)한다.

단지, 힙구축을 할 필요성...에, 최상단으로 옮겨진 값만을 비교하면서 구축해도
기존 구축된 힙값들은 변화하지 않아도 되므로
위의 함수에 for (i=parse...) 부분이 i=1 이면 거의모두(?) 해결된다.

물론, 최종값을 당겨온 의미를 부여하기 위해
최상단에 값을 옮기기 전 L--; (힙의 크기 축소) 를 꼭 해야한다.

*주의* L<=0 인 경우에 대한 대처법은 따로 적지 않았다.

a[1]=a[L]; L--; i=1;

// for 문 외 상동
k=i; if (k+1<=L)  if (isrightLess(a[k], a[k+1])) k++; // k=k+1;
while (k<=L) {
  up=parseInt(k/2);
  if (isrightLess(a[k], a[up])) break;
  sv=a[k]; a[k]=a[up]; a[up]=sv;

  k=k*2;
  }
// -- for 문 외 상동 end

...

NowMark killofki@.

*참고*
내용서술 : killofki
참고서적 : Computer Algorithms in C ( 다다미디어 (1994) )