https://m.blog.naver.com/leeinje66/221594209126

오늘 새롭게 다루게 자료구조는 **우선순위 큐(Priority Queue)**라고 하고 한다.

이름이랑 다르게 큐와는 큰 연관관계가 있지는 않다. 왜냐하면 enqueue와 dequeue 연산이 있다는 점만 비슷하고 dequeue의 조건이 FIFO가 아니라 우선순위에 따라 결정되기 때문이다. 우선순위 큐는 우선순위로 원소가 정렬되는 완전이진트리구조로 표현할 수 있으며 앞에서 다뤘던 것 처럼 완전이진트리를 기대할 수 있는 조건에서는 배열을 이용해 트리를 만든다.

배열이면 배열이지 왜 갑자기 트리 구조를 사용하느냐고 물을 수 있다.

배열로 구현을 한다면 enqueue와 dequeue시 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 해야하고 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위를 비교해야 하기 때문에 매우 불편하다. 설령 연결리스트를 사용한다고 할지라도 데이터를 밀고 당기는 과정만 생략될 뿐이지 여전히 삽입 위치를 찾으려면 저장된 모든 데이터와 우선순위를 비교해야 한다는 단점이 있다. 만일 **힙(Heap)**이라는 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같아야 하는 완전이진트리 자료구조를 사용해서 우선순위 큐를 표현한다면 상단의 단점을 모두 해결할 수 있을 뿐만 아니라 연산 속도도 빨라진다.

힙의 삽입과정은 다음과 같다.

①. 힙의 가장 끝에 새로운 원소를 삽입한다. ②. 부모와 우선순위를 비교해서 높으면 자리를 바꾼다. ③. 반복한다.

이때, 힙이 연결리스트가 아니라 배열로 되어 있으므로 특정 노드에 대해 부모 노드를 고를 수 있는 방법이 필요하다.

앞선 포스트에서 아주 살짝 언급을 했었는데, 완전이진트리가 배열로 구현되어 있을 때, 인덱스의 2배는 왼쪽 자식노드, 2배 + 1은 오른쪽 자식노드 그리고 ÷2는 부모노드를 의미한다.

∙ 힙은 완전이진 트리이다.

∙ 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다.

∙ 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.

∙ 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다.

∙ 우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정한다

# 개인적으로 교재에 나와있는 소스코드가 많이 복잡하다고 느껴졌다. 그래서 ADT만 보고 내가 스스로 배열로 힙을 구현해보았다. #

#include <stdio.h> #include "PriorityQueue.h" void HeapInit(Heap* heap) { heap->numOfData = 0; } // 원소 개수 초기화 int HIsEmpty(Heap* heap) { return heap->numOfData == 0; } // 참.거짓 판별 void HInsert(Heap* heap, Data data, Priority prior) { int cur; heapElement temp; if (heap->numOfData == MAX_HEAP_SIZE) { perror("ERROR::FULL\n"); return; } // 힙이 꽉 찼다면, heap->numOfData += 1; // 1번 인덱스부터 사용할 것이므로 미리 더해준다. cur = heap->numOfData; // 현재 커서 heap->heap[heap->numOfData].data = data; heap->heap[heap->numOfData].priority = prior; // 가장 마지막 위치에 넣어준다. while (TRUE) { if (heap->heap[cur].priority < heap->heap[cur / 2].priority) { // 둘의 위치를 바꿔준다. temp = heap->heap[cur]; heap->heap[cur] = heap->heap[cur / 2]; heap->heap[cur / 2] = temp; cur /= 2; } else break; } } Data HDelete(Heap* heap) { int cur = 1; Data returnVar = heap->heap[1].data; // 반환할 값 미리 저장한다. heapElement temp; heapElement *selectedChild = (heap->heap[cur * 2].priority <= heap->heap[(cur * 2) + 1].priority) ? &(heap->heap[cur * 2]) : &(heap->heap[(cur * 2) + 1]); // 두 자식 노드 중 우선순위가 큰 쪽 고르기 int flag = (heap->heap[cur * 2].priority <= heap->heap[(cur * 2) + 1].priority) ? 0 : 1; if (HIsEmpty(heap)) { perror("ERROR::EMPTY!\n"); return 0; } heap->heap[1] = heap->heap[heap->numOfData]; // 맨 뒤 노드를 맨 위로 올려준다. heap->numOfData--; // 이렇게 하면 맨 뒤 노드를 없앤걸로 칠 수 있다. while (TRUE) { if (heap->heap[cur].priority > selectedChild->priority) { // 둘의 위치를 바꿔준다. temp = heap->heap[cur]; heap->heap[cur] = *selectedChild; *selectedChild = temp; if (flag) cur *= 2; else cur = (cur * 2) + 1; // 왼쪽 자식노드일 경우, 오른쪽 자식노드일 경우 } else break; } return returnVar; }