하나둘셋넷

라이브러리 heap] 기초 개념, 함수

개념

힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리

이 구현에서는 모든 k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]인 배열을 사용

요소는 0부터 count

비교를 위해, 존재하지 않는 요소는 무한으로 간주

가장 작은 요소는 항상 루트인 heap[0]

함수 

1] 힙 불변성을 유지하면서, item 값을 heap으로 푸시

heapq.heappush(heap, item)

2] 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환

ㆍ 힙이 비어 있으면, IndexError가 발생

ㆍ pop 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용

heapq.heappop(heap)

3] 힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 pop하고 반환

ㆍ  결합한 액션은 heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적으로 실행

heapq.heappushpop(heap, item)

4] 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

heapq.heapify(x)

5] heap에서 가장 작은 항목을 팝하고 반환, 새로운 item도 푸시

ㆍ   힙 크기는 변경되지 않는다.

ㆍ   힙이 비어 있으면, IndexError가 발생

heapq.heapreplace(heap, item)

6] 여러 정렬된 입력을 단일 정렬된 출력으로 병합  (예를 들어, 여러 로그 파일에서 타임 스탬프 된 항목을 병합).

ㆍ 정렬된 값에 대한 이터레이터를 반환

heapq.merge(*iterables, key=None, reverse=False)

라이브러리 deque] 호출, 생성, 추가, 제거, 변경

호출

from collections import deque

생성

deq = deque()

추가

# 시작부 부분에 추가
deq.appendleft(10)

# 끝 부분에 추가
deq.append(0)

# 주어진 배열(array)을 순환하면서 데크의 시작 부분에 추가.
deque.extendleft(array): 

# 주어진 배열(array)을 순환하면서 데크의 끝 부분에 추가
deque.extend(array)

# n번 index에 원소를 추가
deque.insert(n, item)

ㆍ 예시) [1, 2, 3]

ㆍextendlef([4,5,6])

→ [6, 5, 4, 1, 2, 3]

ㆍextend([4,5,6])

→ [1, 2, 3, 4, 5, 6]

제거

# 처음 부분에서 제거
deq.popleft()

# 끝 부분에서 제거
deq.pop()

# item을 데크에서 찾아 삭제
deque.remove(item)

# 모든 원소를 제거
deque.clear()

변경

# 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).
deque.rotate(num)

# 원소의 위치를 좌우 반전
deque.reverse()

ㆍ 예시) deque가 [1, 2, 3, 4, 5]이고, rotate(1)을 호출

→  결과는 [5, 1, 2, 3, 4]

∵  각 요소가 오른쪽으로 한 칸씩 이동.

ㆍ  rotate(-1)을 호출하면, 결과는 [2, 3, 4, 5, 1]