9. Priority Queues, Heaps, and Graphs

Heap

complete binary tree & 조상>자식

ReheapDown

노드가 heap의 규칙을 어기고 있을 때 하는 것 노드의 자식노드 중 자기보다 크고 둘중에 큰것을 고른다음 바꾼다. 이과정을 반복해서 자기 자리를 찾는다.

ReheapUp

조상노드가 자기보다 작다면 올라가는 것

Removing the largest element

1. bottom rightmost element를 root로 가져옴
2. bottom rightmost element를 삭제
3. root를 ReheapDown 해줌

Inserting new element

1. bottom leftmost place에 삽입
2. ReheapUp 해줌

Priority Queue

only the highest-priority element만 접근 가능

구현방법
- unsorted list: dequeue할때 다 훑어봐야됨
- array-based sorted list: enqueue할 때 귀찮음
- linked sorted list: enqueue again is O(N)
- binary search tree: 뺄때나 넣을 때나 평균적으로 O(logN)이 걸림
- heap: 가장안좋을때도 뺄때 넣을 때 O(logN) 보장 (가장 편함)

Dequeue

제일 위에가 큰 값이니까 젤 아래에서 오른쪽값이랑 바꾼다음에 젤 아래 오른쪽 값 dequeue해주고 root값 reheapDown
하면 됨

Enqueue

제일 아래에 왼쪽끝에 추가해준다음에 reheapUp 해주면 됨

Graph

verices와 edge로 이루어진 물체
tree도 그래프 중 하나임
complete graph: 모든 vertex가 다른 vertex들과 연결되어있음
weighted graph: edge에 가중치가 있
directed와 undirected가 있음, directed는 edge 쓸때 순서조심해야함

complete directed/undirected graph with N vertices의 edge갯수는?
=> directed일 경우 N*(N-1)이고 undirectd일 경우 N*(N-1)/2이다.

Adjacency Matrix

1차원은 vertices를 나타내고 이차원 값들은 edge의 weight를 나타냄

Adjacency List

1D array는 vertices를 나타내고 리스트는 vertices랑 인접한 vertices와 edge를 나타냄

Graph searching

Depth-First-Search
깊이 우선 탐색이다. stack을 이용하여 구현한다.
우선 시작 vertice를 stack에 넣는다=>stack에서 pop 해주고 pop한 vertice와 가장 인접한거 삽입해준다.
또 pop해주고 push하는 과정을 반복하다가 pop한게 찾던거라면 하던 걸 멈춘다.