이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.


■ 힙 정렬 개념
힙(heap)은 우선순위 큐(priority queue)의 일종으로 우선순위가 높은 요소를 효율적으로 관리하는 자료구조
힙은 배열 또는 연결리스트를 이용한 나무구조로 구현
힙은 부가적 메모리를 필요로 하지 않으며 매우 빠른 성능을 갖음
입력 자료에 무관하게 고른 성능을 보임
힙은 n개의 레코드로 구성된 입력 파일을 하나의 최대 힙(max heap) 즉, 각 노드에 저장되어 있는 원소의 값이 서브노드에 저장되어 있는 원소의 값보다 큰 전이진 트리 구조로 만드는 것
레벨 l 에서 노드의 수가 2l-1< n <2l+1 을 만족하여 레벨 l 상에서 모든 노드들은 가능하면 왼쪽의 위치에 존재하게 됨

■ 우선순위 큐(Priority Queue)

어떤 자료 구조를 의미하는 것이 아니라, 다만 스택 또는 큐 등을 이용하여 각각 우선순위를 갖는 자료를 관리하는 추상적인 개념

생성(construct) : N개의 자료로 우선순위 큐를 생성함
         생성 = N번의 삽입
삽입(insert) : 우선순위 큐에 새로운 자료를 삽입함
제거(remove) : 가장 높은 우선순위를 갖는 자료를 제거함
대치(replace) : 가장 높은 우선순위를 갖는 자료와 새로운 자료를 바꿈
         대치 = 제거 + 삽입
변경(change) : 우선순위 큐 내에 있는 자료의 순위를 변경함
         변경 = 삭제 + 삽입
삭제(delete) : 우선순위 큐 내에 있는 임의의 자료를 삭제함
결합(join) : 두개의 우선순위 큐를 결합하여 큰 우선순위 큐를 생성함

■ 힙(Heap)

키 값의 크기로 우선순위를 결정하는 자료구조
힙은 나무구조로 표현되는데, 이때 부모의 키 값은 반드시 두 자식의 키 값보다 작으면 않된다.
루트 노드에는 키 값이 가장 큰 자료가 위치하게 된다.
단말노드에 삽입된 자료는 우선순위를 맞추기 위해 상위 노드와 비교 후 교환되어져야 한다.

― 최단말 노드에 삽입된 자료는 부모와 비교된다.
― 큰 값을 갖는 경우 부모와 교체된다.
― 계속해서 상위에 있는 부모와 비교되고 크면 교체된다.

반대로 가장 큰 값을 갖는 루트 노드를 제거하는 경우

― 먼저 뿌리 노드의 자료를 제거한다.
― 뿌리 노드가 비어 있으므로 최단말 노드(min)의 자료를 임시로 뿌리에 옮긴다.
― 크기가 작은 노드(min)가 루트를 차지하고 있으므로 아래의 두 자식 노드중에서
   큰 값을 갖는 자료가 임시 자료(min)와 교체된다.
― 아래 레벨로 밀려난 임시 노드(min)는 또 다시 자식 노드와 비교되고 그중에서
   큰 값을 갖는 노드와 교체된다.
― 임시 노드(min)의 자식 노드가 더 작은 값을 갖는 곳 까지 반복 수행된다.


■ 배열로 트리 구현

연결리스트를 이용하면 부모 자식관계를 포인터로 직접 결합 가능
배열을 이용하게되면 첨자를 조작하여 간접적으로 연결해야 함
- 링크를 저장할 공간을 필요로하지 않는 장점을 가짐

- 불균형 트리의 경우 빈 노드를 위해서도 배열 공간을 확보해야 함

- 따라서 균형 트리(balanced tree)에 대해서 배열을 이용한다

힙은 균형 트리이므로 배열을 이용하는 것이 유리함
  
  


■ 힙 정렬의 방법                                          

▷ 힙을 생성
- 힙의 크기를 배열의 크기로 하고 BuildHeap을 통해 힙조건에 맞게 수정하는 방식
- 배열에 저장은 초기 자료의 순서대로 힙이라 가정하고 트리로 구성함
― 부모 노드는 항상 두 자식 보다 큰 값을 가짐
- BuildHeap을 통해 하나씩 제자리를 찾아 내려보냄    


▷ 제거 동작을 반복 수행
― 가장 큰 값을 갖는 루트에서 제거 동작을 수행하고
― 루트가 없는 힙에서는 최단말 노드가 임시로 루트가 되며 제자리를 찾아 내려가게 됨
― 루트에서 뽑아낸 자료는 임의 배열에 끝에서부터 차례로 저장함



■ 힙 정렬 알고리즘
-------------------------------------------------------------------------------
#define LeftChild(i) (2*(i))

void PercDown (int A[ ], int i, int N)         /*  BuildHeap 수행*/
      {
            int Child, Temp;                           /*Temp는 루트의 값을 보관 */
/*1*/    for(Tmp=A[i]; LeftChild(i)<=N; i=Child)
            {
/*2*/          Child=LeftChild(i);
/*3*/          if(Child!=N && A[Child+1] > A[Child])
/*4*/              Child++;
/*5*/          if( Temp<A[Child])                /*  루프를 돌면서 루트의 값이 */
/*6*/              A[i]=A[Child];                  /*  자기의 위치로 내려옴  */
                  else
/*7*/               break;
            }
/*8*/    A[i]=Temp;
      }

void Heapsort(int A[ ],int N)
       {
               int i;
/*a*/       for( i  = N/2; i > 0; i--)           /*  BuildHeap 호출*/
/*b*/           PercDown(A, i, N);
/*c*/       for( i = N;  i >= 2; i--)
               {
/*d*/          Swap(&A[1], &A[i]);         /* DeleteMax  루트의 값을 제일 뒤로  */
/*e*/          PercDown(A, 1, i-1);         /* 제일 뒤에 있던 값이 루트에서 자기 위치로 */
               }                                           /*  BuildHeap 호출*/
        }
-------------------------------------------------------------------------------  



■ 성능

▷ MaxHeap을 만들어서 DeleteMax를 반복 수행하여 정렬
▷ N을 입력 파일의 크기라 하면 BuildHeap O(N),  N번 DeleteMax O(NlogN)
▷ BuildHeap은 내부노드(총 N/2개)에서만 수행되면 됨
- 단말노드는더이상내려갈곳이없으므로을적용할필요가없음
- N/2 노드(마지막 내부노드 위치)부터 뿌리 노드까지만 적용되면 됨
- 적용 범위가 반으로 줄었기 때문에 성능면에서 크게 향상된다. O(NlogN)
▷ 이론적으로 이상적인 O(NlogN)이나 실제 수행시간 길다.
▷ 뛰어난 성능을 가지면서도 추가적인 메모리를 필요로 하지 않음