[자료구조/알고리즘] 우선순위 큐, 힙, 힙 정렬 파이썬 구현

자료 출처: https://youtu.be/AjFlp951nz0

1. 우선순위 큐

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

• 단순히 리스트를 이용하여 구현하는 방식: 삽입시 O(1), 삭제시 O(N)의 시간복잡도
• 힙(heap) 자료구조를 이용하여 구현하는 방식: 삽입, 삭제시 각각 O(logN)의 시간복잡도

2. 힙 (Heap)

완전 이진 트리의 일종인 자료구조로, 항상 루트 노드를 먼저 제거한다.

• 최소 힙 (Min Heap)
  • 루트 노드가 가장 작은 값을 가짐
  • 값이 작은 데이터가 우선적으로 제거됨
  • 따라서 최소 힙에 넣었다 빼면 오름차순으로 정렬됨(작은 데이터부터 제거되므로)
• 최대 힙 (Max Heap)
  • 루트 노드가 가장 큰 값을 가짐
  • 값이 큰 데이터가 우선적으로 제거됨
  • 따라서 최대 힙에 넣었다 빼면 내림차순으로 정렬됨(큰 데이터부터 제거되므로)
• 힙에 새로운 원소가 삽입될 때: O(logN)의 시간 복잡도로 힙의 성질을 유지할 수 있다.
• 힙에서 원소가 제거될 때: O(logN)의 시간 복잡도로 힙의 성질을 유지할 수 있다. 원소 제거시 가장 마지막 노드가 루트 노드의 위치에 오도록 한 후, 루트 노드에서부터 하향식으로(더 작은 자식 노드로) heapify()

3. 힙 정렬 (Heap Sort)

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업만으로도 정렬이 수행된다.

• 시간 복잡도: O(NlogN) 즉 퀵 정렬, 병합 정렬 등과 같은 시간 복잡도

4. 우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예제

import heapq
# 파이썬의 heapq 라이브러리는 기본적으로 min heap을 지원한다. 즉, 작은 값부터 우선적으로 제거하는 오름차순 정렬

def heap_sort(iterable):
    h = [] # 힙
    result = []
    
    # 힙에 모든 데이터를 삽입 후 꺼내는 작업만으로도 정렬 완료
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value) # h(힙)에 heappush를 해줌 즉 heapq라이브러리가 자동으로 최소 힙 방식으로 삽입해줌
    
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 result에 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h)) # heapq라이브러리가 최소힙의 가장 작은 값부터 heappop해줌 따라서 오름차순 정렬
        
    return result
    
    
# 내림차순 정렬

def heap_sort_desc(iterable):
    h = []
    result = []
    
    for value in iterable:
        heapq.heappush(h, -value)
        
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
        
    return result