자료구조 - Chapter 09

우선 순위 큐

우선 순위 큐(Queue)

우선 순위 큐의 연산 결과는 들어간 순서에 상관 없이 우선 순위가 높은 데이터가 먼저 나오는 것이다.

• enqueue : 우선 순위 큐에 데이터를 삽입하는 행위
• dequeue : 우선 순위 큐에서 데이터를 꺼내는 행위

우선 순위 큐 구현 방법

• 배열을 기반으로 구현하는 방법
• 연결 리스트를 기반으로 구현하는 방법
• 힙(heap)을 이용하는 방법

하지만 배열과 연결 리스트로 구현할 경우 삽입 위치를 찾기위해 처음부터 마지막 까지 자료를 모두 비교 해야하는

단점이 존재한다. 따라서 힙을 이용하여 구현한다.

 

힙(heap) 소개

힙은 이진트리이며 완전 이진 트리이다. 그리고 모든 저장된 값은 자식 노드보다 크다.

따라서 최 상단 루트 노드는 가장 큰 값을 갖는다.

 

예제 : 힙 구현하기(Heap)

힙을 기반으로 하면 트리의 높이에 해당하는 수만큼만 비교연산을 진행한다.

트리의 높이가 늘어날 때 마다 비교 연산의 횟수가 증가한다.

• 힙 기반 데이터 저장의 시간 복잡도 : O(log2N)
• 힙 기반 데이터 삭제의 시간 복잡도 : O(log2N)

힙 구현

ex9-1 SimpleHeap.c

0.00MB

SimpleHeap.c

0.00MB

SimpleHeap.h

0.00MB

예제 : Heap 우선 순위 비교 함수로 구현

ex9-2 Heap.c

0.00MB

UsefulHeap.c

0.00MB

UsefulHeap.h

0.00MB

예제 : Heap을 이용하여 우선순위 큐 구현하기

ex9-3PriorityQueue.c

0.00MB

PriorityQueue.c

0.00MB

PriorityQueue.h

0.00MB