heap 정렬

 

u      히프(heap)를 이용해 정렬

          ･ 히프 : 우선순위 큐의 일종

Ø       정렬할 원소를 모두 공백 히프에 하나씩 삽입

Ø       한 원소씩 삭제 →제일 큰 원소가 삭제됨

Ø       이 원소를 리스트의 뒤에서부터 차례로 삽입

Ø       오름차순으로 정렬된 리스트를 생성

HeapSort(a[])

   n ← a.length - 1;  // n은 히프 크기(원소의 수)

                       // a[0]은 사용하지 않고 a[1 : n]의 원소를 오름차순으로 정렬

  for (i ← n/2; i ≥ 1; i ← i-1) do          // 배열 a[]를 히프로 변환

       heapify(a, i, n);                       // i는 내부 노드

  for (i ← n-1; i ≥ 1; i ← i-1) do {        // 배열 a[]를 오름차순으로 정렬

       temp ← a[1]; // a[1]은 제일 큰 원소

       a[1] ← a[i+1]; // a[1]과 a[i+1]을 교환

       a[i+1] ← temp;

       heapify(a, 1, i);

   }

end heapSort()

heapify(a[], h, m)
       // 루트 h를 제외한 h의 왼쪽 서브트리와 오른쪽 서브트리는 히프
       // 현재 시점으로 노드의 최대 레벨 순서 번호는 m
   v ← a[h];
  for (j ← 2*h; j ≤ m; j ← 2*j) do {
      if (j <m and a[j] <a[j+1]) then j ← j+1;  
                                 // j는 값이 큰 왼쪽 또는 오른쪽 자식 노드
      if (v ≥ a[j]) then exit;
      else a[j/2] ← a[j];       // a[j]를 부모 노드로 이동
   }
   a[j/2] ← v;
end heapify()

void sorting()

{

    int i;

    for(i=ARRSIZE/2;i>=1;i--)

        heapify(i,ARRSIZE);

    for(i=ARRSIZE-1;i>-1;i--)

    {

        swap(1,i+1);

        heapify(1,i);

    }

}

void heapify(int h, int m) //힙화 시키는 함수.

{

    int j,v;

    v=buf[h];

    for(j=2*h;j<=m;j*=2)

    {

        if(j<m&&buf[j]<buf[j+1]) j++;

        if(v>=buf[j]) break;

        else buf[j/2] = buf[j];

    }

    buf[j/2] = v;

}

-      제자리 정렬이지만 불안정적

-      N 개의 원소를 정렬하는데 N logN 단계가 필요함

-      입력 배열의 순서에 민감하지 않음

-      내부 루프가 퀵 정렬보다 약간 길어서 평균적으로 퀵 정렬보다 2배 정도 느림