[ 들어가기 전에 ]
[ 일상에서의 우선순위 큐 ]
일정한 루틴으로 살아가는 사람에게 병원 , 미팅등의 우선순위가 높은 일이 생기면 그것을 먼저 처리한다 .
혹은 , 우체국에서 먼저 들어온 일반우편보다 빠른 등기를 먼저 처리한다 .
위의 경우들은 일이 들어온 순서가 아닌 , 우선순위에 따라 일을 처리한다 . 우선순위큐 역시 마찬가지이다 .
[ 우선순위 큐 ]
[ 우선순위 큐의 정의 ]
큐 (Queue)는 먼저 들어간 요소가 먼저 나오는 (FIFO)자료구조이다 .
우선순위 큐는 큐와 같이 동작하지만 "우선순위 속성을 가지는 데이터를 다룬다"는 점에서 차이가 있다 .
둘의 차이는 삽입과 제거 연산이 어떻게 동작하느냐에 있다 .
우선순위큐는 새 요소에 우선순위를 부여하여 큐에 삽입하고 가장 높은 우선순위를 갖는 요소부터 빠져나오도록 한다 .
[ 우선순위 큐의 삽입연산 ]
우선순위큐의 각 요소는 우선순위를 가진다 . 큐의 삽입시 가장 뒤에 넣는것이 아니라 순차적으로 우선순위를 비교
, 올바른 자리에 넣어준다 . 그러나 순차적인 비교는 너무나도 비효율적이다 . 이는 뒤에서 해결해보자 .
[ 우선순위 큐의 제거연산 ]
전단을 제거하여 반환하면 된다 .
[ 우선순위 큐의 구현 ]
우선순위 큐의 삽입을 위해 순차 탐색이 아닌 정렬 , 이진탐색등의 효율적인 방법을 쓸 수는 없을까?
이런 고민을 해결 할 수 있는 힙에 대해 알아보자 .
[ 힙 ]
[ 힙의 정의 ]
한글철자 / 영문철자가 같음에도 지금까지 알던 힙 (자유저장소)이 아닌 , 힙순서 속성을 만족하는 완전 이진트리를 말한다.
- 힙순서 속성은 트리내의 모든 노드가 부모노드보다 크다는 규칙이다 (루트노드는 제외)
- 완전이진트리는 최고깊이를 제외한 모든 깊이의 노드들이 완전히 채워져있는 이진트리를 말한다 . (왼쪽부터 차곡 차곡)
위의 힙을 봤을때 이진탐색이 가능해보이지만 , 부모보다 크다는 규칙을 지킬뿐 순차탐색으로만 검색이 가능하다 .
이런 힙을 사용하는 이유는 "힙에서 가장 작은 데이터를 갖는 노드는 루트노드이다" 라는 사실이다 .
힙의 연산은 새 노드를 삽입하는 연산 / 루트노드를 없애는 최소값 삭제 연산 두가지뿐이다 .
[ 힙의 연산 - 새 노드 삽입 ]
새 노드의 삽입은 다음 3단계를 거쳐 수행된다 .아래에서 부터 마치 거품이 올라오는 형상이다 .
- 힙의 최고 깊이 , 최 우측에 새 노드를 추가한다 . 이때 힙은 완전 이진트리를 유지하도록 한다 .
- 삽입한 노드를 부모와 비교한다 , 부모보다 크다면 종료 - 아니라면 3번째 단계를 수행한다 .
- 부모보다 작으면 부모와새 노드의 위치를 바꾼다 . 다시 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; //배열의 사용 사이즈
}
[ 힙의 삽입 구현 ]
다음은 힙의 삽입을 구현한 코드이다 .
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));
}
}
'자료구조' 카테고리의 다른 글
[자료구조] 우선순위 큐와 힙 - 03 . 우선순위 큐 구현 (0) | 2023.04.03 |
---|---|
[자료구조] 우선순위 큐와 힙 - 02 . 힙 구현 (0) | 2023.03.31 |
[ 자료구조 ] 탐색 - 04 - 3 . 레드 블랙 트리 <구현> (1) | 2023.03.12 |
[ 자료구조 ] 탐색 - 04 - 2 . 레드 블랙 트리 <삭제> (0) | 2023.03.10 |
[ 자료구조 ] 탐색 - 04 - 1 . 레드 블랙 트리 <회전 , 삽입> (0) | 2023.03.07 |