1. Heap

• Shape : complete binary tree → Array로 Heap 표현
• Order : Parents value > child values
• InsertItem() → ReheapUP사용, complete tree가 유지되도록 값을 넣고 그 값보다 큰 값이 나올 때 까지 parent랑 swap

2. Priority Queue

• 제일 큰 값 or 작은 값을 바로 뽑아낼 수 있는 Queue

• Array로 구현할 시 find a highest prority → O(N)

  → Heap으로 구현하기!!

• Dequeue(가장 큰 값 return) → ReheapDown사용, leaf 노드의 맨 오른쪽 값을 root로 복사 하고 그 노드를 지운 뒤 child랑 계속 비교하며 swap

  

• BIg - O

3. Graph

3-1. Adjacency Matrix vs. List

• Adjacency Matrix
  • dense한 그래프에 좋다
  • 두 정점이 연결돼있는지 아닌지 바로 파악 가능
• Adjacency List
  • sparse한 그래프에 좋다
  • 특정한 정점에 인접한 정점들을 빠르게 찾을 수 있음.

3-2. Depth First Searching(DFS)

• Stack을 사용하여 구현

1. Stack에서 Pop
2. pop된 노드를 방문
3. stack에 pop된 노드의 인접 노드를 push