[Data Structure] Priority Queues, Heaps, Graphs and Sets

1. 우선순위 큐

• 우선순위를 가지는 Queue이다. 기존의 Queue에 priority라는 변수를 추가적으로 선언, Queue를 dequeue할 때, 이 Priority를 기준으로 dequeue한다.
• 이때, 동일한 Priority를 가지고 있다면, FIFO로 dequeue한다.

2. 힙

• Heap은 Binary Search Tree와 유사한 자료구조다. 이는 BST에 우선순위 큐를 위하여 만들어진 자료구조로, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아낼 수 있도록 만들어진 자료구조이다.
• max Heap
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• min Heap
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• 구현은 다음 포스팅을 참조하면 좋다.

https://waterglass0105.tistory.com/20

Sort

3. 그래프

• 그래프는 노드의 집합과 노드를 서로 연결하는 에지 집합으로 구성된 데이터 구조이다.

G = (V,E)

 

• 용어
  • Vertex: 그래프에 존재하는 노드
  • Edge(arc): 그래스에서 두 노드 사이의 연결을 나타내는 정점 쌍
  • Undirected graph: Edge가 방향을 가지지 않는 그래프
  • Directed graph: Edge가 방향을 가지는 그래프

vector<dataType> graph[MAX+1];

// if connect graph 0->1

graph[0].push_back(1);

// if connect graph 0<->1

graph[1].push_back(0);

4. 집합

• 중복되는 원소가 없다. C++의 경우 STL에서 제공한다.

set<dataType> name;

https://cplusplus.com/reference/set/set/

https://cplusplus.com/reference/set/set/