[자료구조] 우선순위 큐와 힙 - 01 . 우선순위 큐와 힙

[ 들어가기 전에 ]

[ 일상에서의 우선순위 큐 ]

일정한 루틴으로 살아가는 사람에게 병원 , 미팅등의 우선순위가 높은 일이 생기면 그것을 먼저 처리한다 .

혹은 , 우체국에서 먼저 들어온 일반우편보다 빠른 등기를 먼저 처리한다 . 

위의 경우들은 일이 들어온 순서가 아닌 , 우선순위에 따라 일을 처리한다 . 우선순위큐 역시 마찬가지이다 .

 

[ 우선순위 큐 ]

[ 우선순위 큐의 정의 ]

큐 (Queue)는 먼저 들어간 요소가 먼저 나오는 (FIFO)자료구조이다 .

우선순위 큐는 큐와 같이 동작하지만 "우선순위 속성을 가지는 데이터를 다룬다"는 점에서 차이가 있다 . 

 

둘의 차이는 삽입과 제거 연산이 어떻게 동작하느냐에 있다 .

우선순위큐는 새 요소에 우선순위를 부여하여 큐에 삽입하고 가장 높은 우선순위를 갖는 요소부터 빠져나오도록 한다 .

 

[ 우선순위 큐의 삽입연산 ]

우선순위큐의 각 요소는 우선순위를 가진다 . 큐의 삽입시 가장 뒤에 넣는것이 아니라 순차적으로 우선순위를 비교

, 올바른 자리에 넣어준다 .  그러나 순차적인 비교는 너무나도 비효율적이다 . 이는 뒤에서 해결해보자 .

 

[ 우선순위 큐의 제거연산 ]

전단을 제거하여 반환하면 된다 .

 

[ 우선순위 큐의 구현 ]

우선순위 큐의 삽입을 위해 순차 탐색이 아닌 정렬 , 이진탐색등의 효율적인 방법을 쓸 수는 없을까?

이런 고민을 해결 할 수 있는 힙에 대해 알아보자 .

 

[ 힙 ]

[ 힙의 정의 ]

한글철자 / 영문철자가 같음에도 지금까지 알던 힙 (자유저장소)이 아닌 , 힙순서 속성을 만족하는 완전 이진트리를 말한다.

• 힙순서 속성은 트리내의 모든 노드가 부모노드보다 크다는 규칙이다 (루트노드는 제외)
• 완전이진트리는 최고깊이를 제외한 모든 깊이의 노드들이 완전히 채워져있는 이진트리를 말한다 .                            (왼쪽부터 차곡 차곡)

위의 힙을 봤을때 이진탐색이 가능해보이지만 , 부모보다 크다는 규칙을 지킬뿐 순차탐색으로만 검색이 가능하다 .

이런 힙을 사용하는 이유는 "힙에서 가장 작은 데이터를 갖는 노드는 루트노드이다" 라는 사실이다 .

 

힙의 연산은 새 노드를 삽입하는 연산 / 루트노드를 없애는 최소값 삭제 연산 두가지뿐이다 .

 

[ 힙의 연산 - 새 노드 삽입 ]

새 노드의 삽입은 다음 3단계를 거쳐 수행된다 .아래에서 부터 마치 거품이 올라오는 형상이다 .

1. 힙의 최고 깊이 , 최 우측에 새 노드를 추가한다 . 이때 힙은 완전 이진트리를 유지하도록 한다 .
2. 삽입한 노드를 부모와 비교한다 , 부모보다 크다면 종료 - 아니라면 3번째 단계를 수행한다 .
3. 부모보다 작으면 부모와새 노드의 위치를 바꾼다 . 다시 2번부터 수행한다 .

[ 힙의 연산 - 최소값 삭제 ]

"힙에서 가장 작은 데이터를 갖는 노드는 루트노드이다 ." 최소값을 삭제함은 루트노드를 삭제함과 같다 .

삭제이후 힙 순서 속성의 유지가 해당 문제의 관건이다 . 루트노드의 삭제후 처리는 다음 3 단계를 거친다 .

1. 힙의 루트에 최고깊이 최 우측 노드를 루트 노드로 옮긴다 . (힙의 순서 속성이 파괴됨 )
2. 옮겨온 노드의 양쪽 자식을 비교 , 작은쪽 자식과 위치를 교환한다 .(힙 순서 속성을 치키려면 부모는 양쪽 자식 모두보다 작아야 하기에 작은쪽 자식과 교환한다 .)
3. 양쪽 자식보다 값이 작거나 / 잎노드가 된다면 삭제연산을 종료 , 아니라면 2번부터 반복한다 .

[ 힙의 구현 ]

이진트리를 구현했던것처럼 링크드 리스트를 통해 구현하면 될까?

=>아니다 . 링크드 리스트를 통한 구현은 힙의 가장 마지막 노드 (최고 깊이 노드)를 찾음에 어려움이 있다 .

그렇기에 힙의 구현에는 배열이 더 인기있게 쓰인다 .

 

힙은 완전이진트리이며 , 배열은 완전 이진 트리의 구현에 좋은 자료구조이다 .

완전이진트리를 배열로 나타내는 방법은 다음과 같다

• 깊이 0의 노드는 배열의 0번째 요소에 저장한다 .
• 깊이 1의 노드는 배열의 1,2 번째 요소에 저장한다 .
• 깊이 2의 노드는 배열의 3,4,5,6 번의 요소에 저장한다
• 즉, 깊이 N의 노드(해당 깊이의 노드 개수는 2의 n승)는 배열의 (2n승)-1 부터( 2의 n승+1)-2번 요소에 저장.

장점은 완전 이진트리인 힙의 각 노드의 위치 , 부모/자식간의 관계등을 배열의 인덱스만으로 알 수 있다는 점이다.

다음의 공식은 배열기반의 완전이진트리의 처리를 간단하게 만든다 .

 

k번 인덱스에 위치한 노드의 각 요소의 인덱스는 다음과 같다 .

• 왼쪽 자식 : 2k+1
• 오른쪽 자식 : 2k+2
• 부모 : (k-1)%2의 몫

[ 힙의 자료구조 선언 ]

힙은 두가지 구조체를 가진다 .

하나는 힙의 각 노드를 표현하는 HeapNode 구조체 / 힙 자체를 표현하는 Heap 구조체

 

Heap구조체의 요소를 살펴보자면

• Capacity는 힙의 용량,즉 Nodes 배열의 크기를
• UsedSize는 실제 배열안에 들어있는 큐 요소의 수를 나타낸다 .

typedef int ElementType;

//힙의 각 노드
typedef struct tagHeapNode{
	ElementType Data;
}HeapNode;

//힙
typedef struct tagHeap{
	HeapNode* Nodes;	//힙배열
    int Capacity;		//배열의 용량
    int UsedSize;		//배열의 사용 사이즈
}

[ 힙의 삽입 구현 ]

다음은 힙의 삽입을 구현한 코드이다 .

realloc에 관하여

배열의 동적할당에 관하여

void Heap_Insert(Heap* heap,ElementType NewData)
{
	int CurrentPosition=heap->UsedSize;						//삽입될 위치
    int parentPosition = HEAP_GetParent(CurrentPosition);	//부모의 위치
    
    //힙이 가득 찼다면
    if(heap->Capacity == heap->UsedSize)
    {
    	//힙의 용량을 2배로 늘려준다
    	heap->Capacity*=2;
        //2배의 크기를 재할당한다
        heap->Nodes = (HeapNode*)realloc(heap->Nodes,sizeof(HeapNode)*heap->Capacity);
    }
    
    //데이터를 넣어준다
    heap->Nodes[CurrentPosition].Data=NewData;
    
    //후속처리 :: 부모보다 클때까지 비교를 이어나간다
    while(CurrentPositoin > 0
    && heap->Nodes[CurrentPosition].Data < heap->Nodes[ParentPosition].Data)
    {
    	//부모 자식의 위치를 변경한다
    	Heap_SwapNode(heap , CurrentPosition,ParentPosition)
        //부모 - 자식의 위치를 업데이트
        CurrentPosition = ParentPostion;
        ParentPostion =Heap_GetParent(CurrentPostion);
    	
    }
    //삽입 완료후 사용 사이즈를 늘려준다
    heap->UsedSize++;
    
    }

[ 힙의 최소값 삭제 구현 ]

힙은 항상 최소값이 루트 즉 ,Nodes의 0 번째 요소에 있음을 염두한다면 이해가 쉬울 것이다 .

void Heap_DeleteMin(Heap* heap, HeapNode* Root)
{
	int ParentPosition =0;
	int LeftPosition =0;
	int RightPosition =0;
    
    //Root에 최소값을 저장한다
    memcpy(Root , &heap->Nodes[0] , sizeof(HeapNode));
    //0번째 요소를 0으로 초기화
    memset(&heap->Nodes[0],0,sizeof(HeapNode));
    
    //크기를 줄여준다
    heap->UsedSize--;
    
    //힙의 첫번째 요소에 마지막 요소의 값을 복사한다
    HEAP_SwapNodes(heap,0,heap->UsedSize);
    
    //자식을 찾는다
    LeftPosition = Heap_GetLeftChild(0);
    RightPosition=LeftPosition+1;
    
    //힙 순서 속성을 만족할때까지 자식노드와의 교환을 반복한다
    while(1)
    {
    	int SelectedChild =0;
        
        //왼쪽 자식이 끝의 값이라면 :: 잎 노드인것
        if(LeftPosition >=heap->UsedSize)\
        break;
        
        //오른쪽 자식이 끝의 값이라면
        if(RightPosition >= heap_UsedSize)
        {
        	//왼쪽 자식이 선택
        	SelectedChld = LEftPosition
        }
        
        //양쪽 자식 둘다 있다면
        else
        {
        	//작은 자식을 선택한다
     		if(heap->Nodes[LeftPosition].Data > heap->Nodes[RightPosition].Data
            	SelectedChld=RightPosition;
            else
            	SelectedChld=LefttPosition;     
        }
        //부모가 값이 더 크다면 (교환 필요)
        if(heap->Nodes[SelectedChld].Data < heap->Nodes[ParentPostion].Data)
        {
        	Heap_SwapNodes(heap,ParentPositon,SelectdChlid);
            //바꾼 노드가 부모가 됨
            ParentPostion = SelectedChild;
        }
        else
        {
        	break; //힙 순서 속성을 만족하므로 정지
        }
        
        //자식의 위치업데이트
        LeftPostion= Heap_GetLeftChld(ParentPostion);
        RightPostion=LeftPostion+1
        
    }
    //만약 힙의 크기가 사용량의 반보다 크가면 크기를 절반으로 줄인다
    if(heap->UsedSize < (heap->Capacity/2))
    {
    	heap->Capacity/=2;
        heap->Nodes = (HeapNode*)realloc(heap->Nodes , sizeof(HeadNode)*heap->Capacity));
    }
    
    
}