[알고리즘]Sorting Algorithm_HeapSort

1. HeapSort

struct heap{
	keytype S[1...n];
	int heapsize;
}

void siftdown(heap& H, index i){
	index parent, largerchild;
    keytype siftkey;
    bool spotfound;
    
    parent=i;
    siftkey=H.S[i];
    spotfound=false;
    while(2*parent<=H.heapsize && !spotfound){
    	if(2*parent<=heapsize && H.S[2*parent+1]<=H.S[2*parent]){
			largerchild=2*parent;
        }else{
        	largerchild=2*parent+1;
        }
        if(siftkey<H.S[largerchild]){
            H.S[parent]=H.S[largerchild];
            parent=largerchild;
        }else{
        	spotfound=true;
        }
    }
    H.S[parent]=siftkey;
}

keytype root(heap& H){
	keytype keyout;
    
    keyout=H.S[H.heapsize];
    i=H.heapsize;
	H.S[1]=H.S[H.heapsize];
	H.heapsize=H.heapsize-1;
    siftdown(H,1);
    
    return keyout; 
}

void removekeys(int n, heap& H, keytype S[]){
	index i;
    
    for(i=n;i>=1;i--){
    	S[i]=root(H);
    }
}

void makeheap(int n, heap& H){
	index i;
    
    for(i=n/2;i>=1;i--){
    	siftdown(H,i);
    }
}

void heapsort(int n, heap& H){
	makeheap(n,H);
    removekeys(n,H,H.S);
}