_02.algorithm_priorityQueue

알고리즘

1. 우선순위 큐(Priority Queue)

• 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용
  • 예. 보석 데이터를 자료구조에 넣었다가 가치가 높은 보석부터 꺼내서 확인해야 하는 경우

자료구조	추출되는 데이터
stack	가장 나중에 삽입된 데이터
queue	가장 먼저 삽입된 데이터
priority queue	가장 우선순위가 높은 데이터

• 우선순위 큐를 구현하는 방법
  1) 단순히 리스트를 이용하여 구현 가능
  2) 힙(heap)을 이용하여 구현 가능
• 데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 아래 표와 같다

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

• 단순히 N개의 데이터를 힙에 넣었다 모두 꺼내는 작업은 정렬과 동일 = 힙 정렬
  • 이 경우 시간 복잡도는 _O(NlogN)_이다

1) 힙(Heap)의 특징

• 힙은 완전 이진 트리 자료구조의 일종
  • 완전 이진 트리는 root 노드부터 시작하여 왼쪽 자식 노드에서 오른쪽 자식 노드 순으로 데이터가 차례로 삽입되는 트리(tree)를 의미
• 힙에서는 항상 root node를 제거
• 최소 힙(min heap)
  • 루트노드가 가장 작은 값을 가짐
  • 따라서 값이 작은 데이터가 우선적으로 제거
• 최대 힙(max heap)
  • 루트 노드가 가장 큰 값을 가짐
  • 따라서 값이 큰 데이터가 우선적으로 제거됨

2) 최소 힙 구성 함수 : Min-Heapify() (python) 언어마다 다를 수 있음

• (상향식) 부모 노드로 거슬러 올라가며, 보모보다 자신이 값이 작으면 위치를 바꾼다
• 최소 힙 예제

import heapq

#오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(headpq,heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3) 최대 힙

import heapq

#내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(headpq,heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]