Heap Application : 힙 정렬 (Heap Sort), 우선순위 큐(Priority Queue)

힙(Heap)정의, 힙 추가 연산 (tistory.com)

 

저번 힙 정의에 이어서, 이번엔 힙 응용에 관해 다뤄본다. Heap Application : Heap Sort, Prioirty Queue

 

 

 

우선순위 큐란?

노드 반환(dequeue) 시에 큐에서 우선 순위가 가장 높거나 혹은 가장 낮은 노드를 먼저 반환 하는 큐

 

 

큐 개념만 알고나서 덥석 이 문제 풀었다가 큐의 응용 버전인 Priority Queue인 것을 알고

당황했던 문제 추가...!

 

[C++] 프로그래머스 - 디스크 컨트롤러 / 우선순위 큐 (tistory.com)

 

 

 

 

힙 정렬이란?

순서 없이 배열된 데이터들을 값에 따라 순서대로 재배열하는 것

-오름차순(ascending)정렬 : 값이 증가하는 순서대로 배열하는 것 (ex. 10->20->30)

-내림차순(descending)정렬 : 값이 감소하는 순서대로 배열하는 것 (ex. 30->20->10)

 

 

void heapsort(int values[], int count)
{
	int i=0;
    ArrayMaxHeap* pHeap=NULL;
    
    pHeap=crateArrayMaxHeap(10);
    if(pHeap != NULL){
    	for(i=0;i<count;i++){
        	insertMaxHeapAH(pHeap, values[i]);
        }
        
        for(i=0;i<count;i++){
        	HeapNode* pNode=deleteMaxHeapAH(pHeap);
            if(pNode != NULL){
            	values[i] = pNode->data;
                free(pNode);
                }
       }
       
       deleteArrayMaxHeap(pHeap);
       }
       else{
       	printf("오류");
        return;
       }
 }