[자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

1. 우선순위 큐(Priority Queue)

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용
• 구현 방법
  • 단순 리스트 이용
  • 힙(Heap) 이용
• 시간 복잡도 비교

  구현 방법	삽입 시간	삭제 시간
  리스트	O(1)	O(N)
  힙(Heap)	O(logN)	O(logN)

• 힙(Heap) 정렬
  • 단순히 N개의 데이터를 힙(Heap)에 넣었다가 모두 꺼내는 작업
  • 시간 복잡도: O(NlogN)

2. 힙(Heap)

• 완전 이진 트리(Complete Binary Tree) 자료구조
  • 루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)
    

    

• 항상 루트 노드(root node) 제거
• 최소 힙(min heap)
  • 루트 노드가 가장 작은 값을 가짐
  • 따라서 값이 작은 데이터가 우선적으로 제거
    

    

• 최대 힙(max heap)
  • 루트 노드가 가장 큰 값을 가짐
  • 따라서 값이 큰 데이터가 우선적으로 제거

• 최소 힙 구성 함수: Min-Heapify()
  • (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치 교체
    

    

• 힙에 새로운 원소가 삽입될 때
  • 새로운 원소가 삽입되었을 때 O(logN)의 시간 복잡도로 힙 성질 유지하도록 할 수 있음
    

    

• 힙에서 원소가 제거될 때
  • 원소가 제거되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있음
    • 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 함
      

      

    • 이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify() 진행
      

      

• 우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예제 - 오름차순 정렬(min부터)
  • Python
    

    import sys
    import heapq
    
    input = sys.stdin.readline
    
    def heapsort(iterable):
        heap = []
        result = []
        
        # 모든 원소를 차례대로 힙에 삽입
        for value in iterable: 
        	heapq.heappush(heap, value)
        # 힙에 삽입된 모든 원소를 차례대로 꺼내서 담기
        for i in range(len(heap)): 
        	result.append(heapq.heappop(heap))
        return result
    
    n = int(input())
    arr = []
    
    for i in range(n):
        arr.append(int(input()))
    
    res = heapsort(arr)
    
    for i in range(n):
        print(res[i])