자료를 표현하고 처리하는 방법 중 하나로 스택과 큐가 있다.
나중에 들어간 데이터가 먼저 나오게 되는 구조
Reference
https://youtu.be/whVUYv0Leg0
먼저 들어가 데이터가 먼저 나오게 되는 구조
Reference
https://youtu.be/W3jNbNGyjMs
우선순위 큐를 구현하는 방법은 다양하지만 리스트와 힙(heap)을 사용하는 경우를 알아보면 다음과 같다.
우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
---|---|---|
리스트 | O(1) | O(N) |
힙(Heap) | O(logN) | O(logN) |
단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다(힙 정렬)
힙은 완전 이진트리 자료구조의 일종이다.
python에서 heapq 라이브러리를 사용해서 힙 자료구조를 활용할 수 있다.
Default = Min-heap -> Max-heap을 쓰기위해서는 마이너스(-)부호를 사용해서 바꿔주면 된다.
힙에서는 항상 루트 노드(root node)를 제거한다.
최소힙(min heap)
최대힙(max heap)
완전 이진 트리(Complete Binary Tree)
루트(root) 노드부터 시작 하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례되로 삽입되는 트리(Tree)
최소 힙 구성 함수 : Min-Heapify()
힙에 새로운 원소가 삽입될 때:
다시말해 데크는 스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있다.
대부분의 경우에 python에서 list보다 효율적인 데이터 조작이 가능하다.
특히나 data의 입출입이 빈번한 알고리즘에서는 그 효과가 더욱 크다.
deque.append(item): item을 데크의 오른쪽 끝에 삽입
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가
deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가
deque.remove(item): item을 데크에서 찾아 삭제
deque.rotate(num): 데크를 num만큼 회전(양수면 오른쪽, 음수면 왼쪽).