[ch10]데크,우선순위 큐

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ]

---

* 데크(deque)

- 앞, 뒤 양쪽 방향에서 element 를 추가하거나 제거할 수 있다.

- 양 끝 element 접근하여 삽입 또는 제거 시, O(n) 이 소요되는 리스트에 반해, O(1) 로  접근 가능

from collections import deque

deq = deque()

deq.append(10)
deq.appendleft(0)

deq.pop()
deq.popleft()

deq.remove(10)

from collections import deque

deq = deque([1,2,3,4,5])

deq.rotate(1) # [5,1,2,3,4]

deq.rotate(-1) # [1,2,3,4,5]

---

* 우선순위 큐

-> 대부분의 우선순위 큐 문제는 heapq 모듈 사용해서 풀이

- heapq 모듈 : 최소 힙(Min heap)지원

import heapq

# 일반적인 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와준다.

heap = []

# 힙에 원소 추가 O(logN)
heapq.heappush(heap, 1)

# 힙에서 원소 삭제 O(logN)
heapq.heappop(heap)

# 최소힙
# [1][2]..이후 요소들이 정렬되어 오름차순인 것은 X
# heappop 할 때, 이진 트리 재배치로 매번 새로운 최소값을 인덱스 0에 위치시키는 것
heap[0] #-최솟값 확인

# 리스트를  힙으로 변환
l = [1,2,3]
heapq.heapify(l)

- k 번째 최소값 / 최대값 찾기에 좋음

: heappop 할 때마다 최소값을 찾아서 pop 하고 그 다음 최소값을 [0] 위치에 갖다놓는다

: 따라서, heappop 을 k 번 호출하면서 최소값을 갱신하면 최종 최소값이 k 번째 최소값이 된다.

import heapq
def kth_smallest(nums, k):
    
    heapq.heapify(nums) 
    for _ in range(k):
        kth_min = heapq.heappop(nums)
    
    return kth_min

nums = [8,6,5,4,25,13]
kth_smallest(nums, 4)