본문 바로가기
Algorithm/Theory

자료 구조 - 우선순위 큐와 힙

by hyunipad 2021. 1. 14.
반응형

먼저 들어간 요소가 먼저 나오는(First-In First-Out) 자료 구조를 큐(Queue)라고 합니다. 우선순위 큐와 그냥 큐의 다른 점은 보통의 큐는 먼저 들어온 요소가 먼저 나가지만, 우선순위 큐에서는 요소에 우선순위를 부여해서 가장 높은 우선순위를 갖는 요소부터 빠져나가게 한다는 점에서 차이가 있습니다.

우선순위의 기준은 프로그래머에게 달려있습니다. 오름차순, 내림차순 등이 기준이 될 수도 있고, 시간의 빠름, 느림 등이 우선순위가 될 수도 있습니다.

 

우선순위 큐의 삽입

 지금의 우선순위 큐의 기준은 값의 오름차순입니다.

우선순위 큐

이 큐에 20의 요소를 삽입한다면, 보통의 큐는 First-In First-Out의 구조로 32 뒤에 붙어야 하지만 우선순위 큐의 기준에 따라 17과 22의 사이에 삽입합니다.

 

우선순위 큐의 삽입

 

 

우선순위 큐의 제거

우선순위 큐의 제거는 보통의 큐와 동일합니다. 전단의 요소를 제거하면 됩니다.

 

 

우선순위 큐의 문제점과 힙

우선순위의 삽입 연산을 할때, 위치를 찾아가기 위한 알고리즘은 순차 탐색입니다.

그런데 우선순위의 큐의 크기가 커지면 커질수록 순차 탐색의 효율은 떨어집니다. 이러한 문제를 해결하기 위해 우선순의 큐와 완전 이진트리가 결합한 형태인 힙(Heap)이 등장하게 됩니다.

 

힙이란 완전 이진 트리에서 모든 노드들이 부모 노드보다 커야 한다는 규칙을 가진 트리 구조입니다.

이 규칙은 힙에서 한가지를 확실히 보장합니다. 바로 힙에서 "가장 작은 데이터는 루트 노드"라는 것이죠.

 

힙은 배열로 나타내는 방법은 다음과 같습니다.

  • 깊이 0의 노드는 배열의 0번 요소에 저장합니다.(루트 노드)
  • 깊이 1의 노드는(모두 2개)는 배열의 1~2번 요소에 저장합니다.
  • 깊이 2의 노드는(모두 4개)는 배열의 3~6번 요소에 저장합니다.
  • 깊이 n의 노드는(2n개)는 배열의 2n-1 ~ 2n+1-2번 요소에 저장합니다.

*공식

  • k번 인덱스에 위치한 노드의 양쪽 자식 노드들이 위치한 인덱스
    • 왼쪽 자식 노드 2k+1
    • 오른쪽 자식 노드 2k+2
  • k번 인덱스에 위치한 노드의 부모 노드가 위치한 인덱스 : (k-2)/2의 몫
typedef struct tagHeapNode {
	int Data;
}HeapNode;

typedef struct tagHeap {
	HeapNode* Nodes;
	int Capacity;
	int UsedSize;
}Heap;

힙의 노드 삽입

힙의 삽입은 3 단계로 구성되어 있습니다.

  1. 힙의 최고 깊이, 최 우측에 새 노드를 추가합니다. 이 때 이진트리의 규칙을 유지해야 합니다.
  2. 삽입한 노드와 부모 노드를 비교해서 삽입한 노드가 부모 노드보다 크면 연산을 종료하고, 삽입한 노드가 작으면 부모 노드와 위치를 바꿉니다. 바꾸고 나면 다시 2번 연산을 반복합니다.
void HEAP_SwapNodes(Heap* H, int Index1, int Index2) {
	int CopySize = sizeof(HeapNode);
	HeapNode* Temp = (HeapNode*)malloc(CopySize);

	memcpy(Temp, &H->Nodes[Index1], CopySize);
	memcpy(&H->Nodes[Index1], &H->Nodes[Index2], CopySize);
	memcpy(&H->Nodes[Index2], Temp, CopySize);

	free(Temp);
}

int HEAP_GetParent(int Index) {
	return (int)((Index - 1) / 2);
}

void HEAP_Insert(Heap* H, int NewData) {
	int CurrentPosition = H->UsedSize; //마지막 인덱스 위치(최고 깊이, 최우측 노드)
	int ParentPosition = HEAP_GetParent(CurrentPosition); //부모 노드 구하기 

	if (H->UsedSize == H->Capacity) {
		H->Capacity *= 2;
		H->Nodes = (HeapNode*)realloc(H->Nodes, sizeof(HeapNode) * H->Capacity); // 메모리 크기 변경
	}

	H->Nodes[CurrentPosition].Data = NewData; // 데이터 넣기

	while (CurrentPosition > 0 && H->Nodes[CurrentPosition].Data < H->Nodes[ParentPosition].Data) { // 부모노드가 더 클때
		HEAP_SwapNodes(H, CurrentPosition, ParentPosition); // 스왑

		CurrentPosition = ParentPosition; // 인덱스도 스왑
		ParentPosition = HEAP_GetParent(CurrentPosition); // 인덱스도 스왑
	}

	H->UsedSize++;
}

 

힙의 최솟값 삭제

힙에서는 노드 삭제가 아니라 힙의 최소값 즉 루트 노드를 삭제하는 알고리즘을 학습합니다. 그 이유는 우선순위 큐와 연관되어있죠,

 

힙에서 루트 노드 삭제한 후의 뒤처리 과정을 다음과 같습니다.

  1. 힙의 최고 깊이, 최우 측에 있는 노드를 루트 노드로 옮겨옵니다.
  2. 옮겨온 노드의 양쪽 자식을 비교하여 작은 쪽 자식과 위치 교환을 합니다.
  3. 옮겨온 노드가 더 이상 자식이 없거나 양쪽 자식보다 작은 값을 갖는 경우에 연산을 종료합니다. 아니면 2번 연산 반복
int HEAP_GetLeftChild(int Index) {
	return (2 * Index) + 1;
}

void HEAP_DeleteMin(Heap* H, HeapNode* Root) {
	int ParentPosition = 0;
	int LeftPosition = 0;
	int RightPosition = 0;

	memcpy(Root, &H->Nodes[0], sizeof(HeapNode)); // Root 에 최소값 저장
	memset(&H->Nodes[0], 0, sizeof(HeapNode));

	H->UsedSize--;
	HEAP_SwapNodes(H, 0, H->UsedSize); // 루트 노드와 마지막 노드 스왑

	LeftPosition = HEAP_GetLeftChild(0);
	RightPosition = LeftPosition + 1;

	while (1) {
		int SelectedChild = 0; // 셀렉트된 노드는 자식 노드중 작은 노드

		if (LeftPosition >= H->UsedSize) {
			break;
		}

		if (RightPosition >= H->UsedSize) {
			SelectedChild = LeftPosition;
		}

		else {
			if (H->Nodes[LeftPosition].Data > H->Nodes[RightPosition].Data) {
				SelectedChild = RightPosition;
			}
			else {
				SelectedChild = LeftPosition;
			}
		}

		if (H->Nodes[SelectedChild].Data < H->Nodes[ParentPosition].Data) { // 부모 노드와 선택된 노드 비교
			HEAP_SwapNodes(H, ParentPosition, SelectedChild); // 부모 노드가 더 크면 스왑
			ParentPosition = SelectedChild; // 스왑 후 다음 노드 이동을 위해 셀렉트된 노드를 부모노드로 지정
		}
		else { // 아니면 빠져나감
			break;
		}

		LeftPosition = HEAP_GetLeftChild(ParentPosition); // 다음 노드로 이동하여
		RightPosition = LeftPosition + 1;
	}

	if (H->UsedSize < (H->Capacity / 2)) {
		H->Capacity /= 2;
		H->Nodes = (HeapNode*)realloc(H->Nodes, sizeof(HeapNode) * H->Capacity);
	}
}

 

힙을 이용한 우선순위 큐의 구현

우선순위 큐에 대해 기억나시나요? 우선순위 큐는 개발자가 임의로 정한 우선순위 규칙에 따라 FIFO가 정해졌습니다.

힙을 이용하여 우선순위 큐를 구현하면 최솟값(최대값) 삭제를 힙을 이용하여 할 수 있습니다.

달라진 점은 힙을 이용한 우선순위 큐를 구현할 때 노드에 우선순위(int)를 넣어서 우선순위를 통하여 최소값 노드를 정해준다는 것입니다. 그리하여 노드를 insert, delete 하고 후처리를 할 때 그 우선순위를 통해 노드의 크고 작음을 계산합니다.

 

void  PQ_Enqueue( PriorityQueue* PQ, PQNode NewNode )
{
    int CurrentPosition = PQ->UsedSize;
    int ParentPosition  = PQ_GetParent( CurrentPosition );

    if ( PQ->UsedSize == PQ->Capacity ) 
    {
        if ( PQ->Capacity == 0 )
            PQ->Capacity = 1;
            
        PQ->Capacity *= 2;
        PQ->Nodes = (PQNode*) realloc( PQ->Nodes, sizeof( PQNode ) * PQ->Capacity );
    }

    PQ->Nodes[CurrentPosition] = NewNode;

    /*  후속 처리. */
    while ( CurrentPosition > 0 
        && PQ->Nodes[CurrentPosition].Priority < PQ->Nodes[ParentPosition].Priority )
    {
        PQ_SwapNodes( PQ, CurrentPosition, ParentPosition );
        
        CurrentPosition = ParentPosition;
        ParentPosition  = PQ_GetParent( CurrentPosition );
    }

    PQ->UsedSize++;
}
void      PQ_Dequeue( PriorityQueue* PQ, PQNode* Root )
{
    int ParentPosition = 0;
    int LeftPosition   = 0;    
    int RightPosition  = 0;    
    
    memcpy(Root, &PQ->Nodes[0], sizeof(PQNode));
    memset(&PQ->Nodes[0], 0, sizeof(PQNode));

    PQ->UsedSize--;
    PQ_SwapNodes( PQ, 0, PQ->UsedSize );

    LeftPosition  = PQ_GetLeftChild( 0 );
    RightPosition = LeftPosition + 1;

    while ( 1 )
    {
        int SelectedChild = 0;

        if ( LeftPosition >= PQ->UsedSize )
            break;

        if ( RightPosition >= PQ->UsedSize )
        {
            SelectedChild = LeftPosition;
        }
        else {
            if ( PQ->Nodes[LeftPosition].Priority > PQ->Nodes[RightPosition].Priority)
                SelectedChild = RightPosition;
            else
                SelectedChild = LeftPosition;                
        }

        if ( PQ->Nodes[SelectedChild].Priority < PQ->Nodes[ParentPosition].Priority)
        {
            PQ_SwapNodes(PQ, ParentPosition, SelectedChild);
            ParentPosition = SelectedChild;
        }
        else
            break;

        LeftPosition  = PQ_GetLeftChild(ParentPosition);
        RightPosition = LeftPosition + 1;
    }

    if ( PQ->UsedSize < ( PQ->Capacity / 2 ) ) 
    {
        PQ->Capacity /= 2;
        PQ->Nodes = 
            (PQNode*) realloc( PQ->Nodes, sizeof( PQNode ) * PQ->Capacity );
    }
}

 

전체 코드는 제 깃허브 주소에서 확인할 수 있습니다.

 

출처 : 뇌를 자극하는 알고리즘

반응형
저작자표시

'Algorithm > Theory' 카테고리의 다른 글

자료 구조 - 링크드 리스트(Linked List)  (0) 2021.01.19
자료 구조 - 이진 탐색 트리(Binary Search Tree)  (0) 2021.01.17
탐색 알고리즘 - 이진 탐색(Binary Search)  (0) 2021.01.14
탐색 알고리즘 - 순차 탐색(Sequential Search)  (0) 2021.01.12
자료 구조 - 레드 블랙 트리  (0) 2021.01.07

관련글

댓글

티스토리툴바