[Data Structure] 8. 우선 순위 큐

이 카테고리에 정리된 내용은 강의시간에 필기한 내용이 주를 이룹니다. 교수님께서 강의 하신 내용들 중에 핵심들과 부가적인 내용들을 요약하여 게시했습니다. 강의시간에 생능출판사의 C언어로 쉽게 풀어쓴 자료구조 책을 사용했기 때문에 정리하는 순서도 이 책의 순서에 따라 하기로 했습니다. 순전히 정리용이기 때문에 시험기간이나 복습용으로는 적절하지만 순수한 학습용으로는 적절하지 않을 수 있습니다.

목록보기

8.1 우선 순위 큐의 데이터 타입

– 우선 순위 큐 (priority queue) : 일반 큐와는 달리 각 데이터의 중요도에 따라 처리의 우선 순위가 결정되는 데이터 타입. 삭제, 탐색 연산이 우선순위에 따라 처리됨.

– 우선 순위 큐 연산의 예시 : create() / init() / is_empty() / is_full() / insert() / delete() / find()

 

8.2 우선 순위 큐의 구현 방법

– 구현 방법에 따른 삽입/삭제 연산의 시간 복잡도

표현방법 / 삽입 / 삭제

순서없는 배열 / O(1) / O(n)

순서없는 연결리스트 / O(1) / O(n)

정렬된 배열 / O(n) / O(1)

정렬된 연결리스트 / O(n) / O(1)

heap / O(logn) / O(logn)

 

8.3 heap

– heap : 완전 이진 트리의 일종으로 우선 순위 큐를 위하여 만들어진 자료구조. 일종의 반 정렬 상태를 유지. 배열로 구현

– max heap : 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진트리(루트의 키값이 가장 큼).

– min heap : 부모노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진트리(leaf의 키값이 가장 큼).

– 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2

– 오른쪽 자식의 인덱스 = 부모의 인덱스 *2 +1

– 부모의 인덱스 = 자식의 인덱스 / 2

 

목록보기