1. 우선순위 큐 (Priority Queue)

스택은 가장 나중에 삽입된 원소 먼저 추출하고, 큐는 가장 먼저 삽입된 요소를 먼저 추출한다. 하지만 우선순위 큐는 어떠한 특정 조건에 따라 우선순위가 가장 높은 요소를 먼저 추출하는 자료형이다. 대표적으로 최댓값 추출이 있다. 예를 들어 큐에 [1, 4, 5, 3, 2]가 들어있고 최댓값을 추출하는 우선순위 큐는 항상 남아 있는 요소들의 최댓값을 먼저 추출하여 [5, 4, 3, 2, 1] 순으로 추출된다.

2. 우선순위 큐 시간 복잡도

우선순위 큐는 배열, 연결 리스트 등의 여러가지 방법으로 구현가능하지만 가장 효율적인 구조는 heap을 사용하는 것이다.

배열을 사용하는 방법

• 정렬이 안된 배열: 삽입 O(1), 삭제 O(N)

• 정렬이 되어있는 배열: 삽입 O(N), 삭제 O(1)

연결 리스트를 사용하는 방법

• 정렬이 안된 리스트: 삽입 O(1), 삭제 O(N)

삽입 시에는 포인터만 변경하여 삽입하면 된다. 삭제 시에 포인터를 따라서 모든 노드를 뒤져보아야 한다.

• 정렬된 리스트: 삽입 O(N), 삭제 O(1)

삽입 시에는 우선순위 값을 기준으로 삽입 위치를 찾아야 한다. 삭제 시에는 첫 번째 노드를 삭제하기만 하면 된다.

힙을 사용하는 방법

• 삽입 O(logN), 삭제 O(logN)

3. 힙 (Heap)

힙(Heap)은 그래프나 트리와는 전혀 관계 없어 보이지만, 트리 기반의 자료구조이다. 힙은 거의 완전한 이진 트리로 우선순위 큐를 위하여 만들어졌다. 즉, 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 파이썬에서는 heapq모듈을 사용하면 되고, 최소 힙만 구현되어 있다.

최소 힙은 부모 노드의 값이 자식 노드의 값 보다 작은 이진 트리이다. 따라서 루트가 결국 가장 작은 값을 갖게 되며 우선순위 큐에서 가장 작은 값을 추출하는 것은 매번 최소 힙의 루트를 가져오는 형태로 구현된다. 반대로 최대 힙은 부모 노드의 값이 자식 노드 값 보다 항상 큰 이진 트리이다. 마찬가지로 가장 큰 값을 추출하려면 최대 힙의 루트를 가져오면 된다. 아래는 최소 힙과 최대 힙의 예시이다.

여기서 중요한 것은 힙은 정렬된 구조가 아니라는 것이다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐, 서로 정렬되어 있지 않다. 오른쪽 자식노드가 왼쪽 노드보다 더 작은 경우도 얼마든지 있을 수 있다. 다시말해, 부모와 자식간의 관계만 정의할 뿐 좌우에 대한 관계는 정의하지 않는다. 이 이유 때문에 힙은 거의 완전한 이진 트리라고 한다.

힙은 완전 이진 트리로 배열에 빈틈없이 배치가 가능하다. 최소 힙을 배열로 표현한 것은 아래와 같다.

트리의 배열 표현의 경우 계산을 편하게 하기 위해 인덱스는 1부터 사용한다.

최소 힙 삽입 연산 (insert)

힙에 요소를 삽입하기 위해서는 업힙 (Up-Heap) 연산을 수행해야 한다.

① 가장 마지막에 요소를 추가한다.

② 부모 값과 비교해 값이 추가하려는 요소의 값이 더 작은 경우 위치를 변경한다.

③ 계속해서 부모 값과 비교해 위치를 변경한다.

두 번째 스왑 이후에 부모 노드인 5보다 더 크기 때문에 더 이상 스왑되지 않고 멈춘다.

최소 힙 삭제 연산 (extract)

힙에 요소를 삽입하기 위해서는 업힙 (Up-Heap) 연산을 수행해야 한다. 추출 할 때는 루트 노드를 추출하면 된다. 이때 시간 복잡도는 O(1)이라고 생각할 수 있지만 추출 이후에 다시 힙의 트기성을 유지하는 작업이 필요하기 때문에 O(logN)이다.

① 루트 노드를 추출한다.

② 추출 후에 비어 있는 루트에 가장 마지막 요소를 올린다.

③ 새로운 루트 노드는 자식 노드와 값을 비교해서 자식보다 크면 내려가는 다운힙 (Down-Heap) 연산을 수행한다.

④ 계속해서 자식 값과 비교해 위치를 변경한다.

세 번째 스왑 이후에 자식 노드가 없기 때문에 더 이상 스왑되지 않고 멈춘다.

4. Heap with Python

heapq 모듈은 이진트리 기반의 최소 힙 자료구조를 제공한다. 최소 힙을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, 가장 작은 값은 항상 인덱스 0에 위치한다. 내부적으로 최소 힙 내의 모든 원소는 항상 자식 원소들 보다 크기가 작거나 같도록 원소가 추가되고 삭제된다. 파이썬 heap 모듈의 heaq.heaappush()는 insert()에, heapq.heappop()은 extract()에 대응된다.

힙에 원소 추가

heapq.heappush(heap, item) : item을 heap에 추가

import heapq

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print(heap)
# [1, 3, 7, 4]

힙에서 원소 삭제

heapq.heappop(heap) : heap에서 가장 작은 원소를 삭제하고 리턴, 비어 있는 경우 IndexError가 호출된다.

print(heapq.heappop(heap))
# 1
print(heap)
# [3, 4, 7]

print(heapq.heappop(heap))
# 3
print(heap)
# [4, 7]

힙의 원소 얻기

print(heap[0])
# 4

기존 리스트를 힙으로 변환

heapq.heapify(x) : 리스트 x를 heap 자료구조로 변환한다. O(N)

a = [4, 1, 7, 3, 8, 5]
heapq.heapify(a)
print(a)
# [1, 3, 5, 4, 8, 7]

최대 힙 만들기

최대힙을 만들때는 (우선순위, 값) 구조의 튜플을 힙에 추가하고, 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 된다.

nums = [4, 1, 7, 3, 8, 5]
h = []

for num in nums:
    heapq.heappush(h, (-num, num))
print(h)
# [(-8, 8), (-7, 7), (-5, 5), (-1, 1), (-3, 3), (-4, 4)]

while h: 
    print(heapq.heappop(h)[1])
'''
8
7
5
4
3
1
'''

k번째 최솟값/최댓값 구하기

def kth_smallest(nums,k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
    kth_min = 0
    for _ in range(k):
        kth_min = heapq.heappop(heap)
    return kth_min

print(kth_smallest([4, 1, 7, 3, 8, 5], 3))
# 4

힙 정렬

def heap_sort(nums):
    heap =[] 
    for num in nums:
        heapq.heappush(heap, num)
    
    sorted_nums = []
    while heap:
        sorted_nums.append(heapq.heappop(heap))
        
    return sorted_nums

print(heap_sort([4, 1, 7, 3, 8, 5]))
# [1, 3, 4, 5, 7, 8]