[자료구조] 9장 Priority Queue

1. Priority Queue

: 우선순위가 높은 데이터가 먼저 나감. 

   배열/연결리스트/힙으로 구현 가능.

 

2. Heap

• 완전 이진 트리
• 최대 힙: 부모 노드의 키 값이 자식노드의 키값보다 크거나 같음
• 최소 힙: 부모 노드의 키 값이 자식노드의 키 값보다 작거나 같음
• 힙은 배열을 이용해 만들면 효율적.
• 완전 이진 트리 -> 각 노드에 번호를 붙임 -> 배열의 인덱스

 

3. Upheap(삽입)

• 새로운 요소가 들어오면 일단 마지막 노드에 이어서 삽입
• 삽입된 위치에서 루트까지의 경로에 잇는 노드들을 비교, 교환
• 키가 부모 노드보다 작거나 같으면 종료.
• O(logn)

 

4. Downheap(삭제)

• 루트 삭제.
• 루트에서부터 단말 노드까지의 노드들을 교환해 힙 성질 만족.
• O(logn)

 

5. 힙정렬

• n개의 요소를 최대 힙에 삽입
• 하나씩 힙에서 삭제해 저장
• 삭제되는 요소들은 값이 감소되는 순서
• 하나 요소 삽입 삭제의 시간 복잡도: O(logn)
• 요소 개수가 n개 이므로 O(nlogn)