[TIL] Day 2 - 자료구조와 알고리즘(2)

큐 (Queues)

1. 환영 큐 (circular queue)

정해진 개수의 저장공간을 돌려가며 이용 ( 시작점 front, 끝점 rear )

#deque
self.rear = (self.rear+1) % self.maxCount
#enque
self.front = (self.front+1) % self.maxCount

2. 우선순위 큐 (priority queue)

원소들의 우선순위에 따라 deque 됨.
Enqueue 할때 우선순서를 유지하면서 push 하고,
연결리스트를 이용하는 것이 시간복잡도 상 효율적이다.
( heap 응용 가능 )

이진트리 (Binary Trees)

모든 노드의 차수가 2이하인 트리

재귀적으로 표현,
비어있는 트리이거나, 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리

힙 (heap)

1. root가 언제나 최대 or 최소값
2. 완전 이진트리

1. 배열을 이용한 이진트리 표현

노드 번호가 배열 인덱스 m 기준으로,

• 왼쪽 자식 : 2 x m
• 오른쪽 자식 : 2 x m+1
• 부모 노드 : m // 2

2. insert(item)

• O( log N )

1. 맨 마지막에 노드 삽입
2. 자리 찾을 때 까지 부모와 크기 비교

3. remove()

• 무조건 root 노드가 return -> 최댓값 혹은 최소값

1. 루트노드 제거
2. 트리 마지막 자리 노드를 임시로 루트 노드로 배치
3. 바뀐 루트부터 자식 노드 중 값과 비교하면서 아래로 이동
   -> 항상 heapify 상태로 유지