우선순위 큐와 heap - python

참고 | 이코테2021 | 우선순위 큐

 

우선순위 큐

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

• 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용
  • ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터꺼내서 확인해야 하는 경우

구현 방법

1. 단순히 리스트 이용해 구현 가능
2. 힙(heap)을 이용해 구현 가능

• 데이터가 N개일 때 구현 방식에 따른 시간복잡도

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

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

 

힙의 특징

최소힙 최대힙

• 힙은 완전 이진 트리 자료구조의 일종
• 힙에서는 항상 루트 노드를 제거한다
• 최소 힙(mini heap)
  • 루트 노드가 가장 작은 값을 가짐
  • 따라서 값이 작은 데이터가 우선적으로 제거됨
• 최대 힙(max heap)
  • 루트 노드가 가장 큰 값을 가짐
  • 따라서 값이 큰 데이터가 우선적으로 제거된다

 

완전이진 트리(Complete Binary Tree)

• 완전 이진 트리란 루트 노드부터 시작해 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미

최소 힙 구성 함수 : Min-Heapify()

• 힙을 구성하기위한 함수의 이름을 보통 Heapify라고 부름
• (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우 위치를 교체
• 부모노드가 자식노드보다 크므로 값을 교환

 

힙에 새로운 원소가 삽입될 때

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

 

힙에서 원소가 제거될 때

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

    

    2삭제 후 마지막 노드인 9를 루트 노드에 넣기

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

 

코드 구현

• 파이썬은 디폴트로 heap정렬 오름차순(Min-heapify)으로 정렬

최소 힙 : Min-heapify

import sys
import heapq
input = sys.stdin.readline
# 입력값
# 5
# 6
# 3
# 1
# 2
# 4

# 결과값 : 1 2 3 4 6

def heapsort(iterable):
    h = []
    result = []
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    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], end=' ')

 

최대 힙 : Max-heapify

• Min-heapify에서 value에 -만 넣어주면 된다

import sys
import heapq
input = sys.stdin.readline

def heapsort(iterable):
    h = []
    result = []
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    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], end=' ')