- toc {:toc}
Heap
-
루트로 올수록 더 크거나 작아지는 완전 이진 트리
-
힙 성질
- 힙의 각 노드에 대해 노드 값은 자식의 값보다 커야 한다.(Maxheap)
-
메모리 힙과 연관성이 있는 것은 아니다.
-
루트가 항상 가장 큰 값이거나 가장 작은 값이다.
-
루트 제거 → 가장 큰 값 추출
- 리프 노드 중 가장 오른쪽 값을 루트로 복사하고 리프 노드 값은 삭제한다.
- 힙 성질에 따라 ReheapDown을 통해 위치를 찾아간다.
template<class ItemType>
void HeapType<ItemType>::MAX_ReheapDown(int root, int bottom)
{
int maxChild;
int rightChild;
int leftChild;
leftChild = root * 2 + 1;
rightChild = root * 2 + 2;
if (leftChild <= bottom){
if(leftChild == bottom){ // 자식이 1개 있는 경우
maxChild = leftChild;
}
else{ // 자식이 2개 있는 경우
if(elements[leftChild] <= elements[rightChild]){
maxChild = rightChild;
}
else{
maxChild = leftChild;
}
}
if(elements[maxChild] == null_val) return;
if(elements[root] < elements[maxChild]){
Swap(elements[root], elements[maxChild]);
MAX_ReheapDown(maxChild, bottom);
}
}
}
- 노드 삽입
- 마지막 빈칸에 넣고 위로 올린다.
template<class ItemType>
void HeapType<ItemType>::MAX_ReheapUp(int root, int bottom)
{
int parent;
if(bottom > root){ // tree가 비어있지 않다면
parent = (bottom - 1) / 2;
if(elements[bottom] > elements[parent]){
Swap(elements[bottom], elements[parent]);
MAX_ReheapUp(root, parent);
}
}
}
Priority Queue
- 다음 방식으로 우선순위 큐를 구현할 수 있다.
- Unsorted Listv - Dequeue → 전체 리스트를 탐색해야 하므로 O(N)
- Array-Based Sorted List → Enqueue 비용이 비싸다 O(N)
- Linked Sorted List → Enqueue 비용이 비싸다 O(N)
- Binary Search Tree → 평균적으로 Enqueue, Dequeue가 O(logN)
- Heap → 최악의 경우에도 O(logN) 이 보장된다.
class FullPQ(){};
class EmptyPQ(){};
template<class ItemType>
class PQType
{
public:
PQType(int);
~PQType();
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Enqueue(ItemType newItem);
void Dequeue(ItemType& item);
private:
int length;
HeapType<ItemType> items;
int maxItems;
};
template<class ItemType>
PQType<ItemType>::PQType(int max){
maxItems = max;
items = new ItemType[max];
length = 0;
}
template<class ItemType>
void PQType<ItemType>::MakeEmpty(){
length = 0;
}
template<class ItemType>
PQType<ItemType>::~PQType(){
delete [] items;
}
template<class ItemType>
void PQType<ItemType>::Dequeue(ItemType& item)
{
if (length == 0)
throw EmptyPQ();
else {
item = items[0];
items[0] = items[length-1];
length--;
items.ReheapDown(0, length-1);
}
}
template<class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
{
if (length == maxItems)
throw FullPQ();
else {
length++;
items[length-1] = newItem;
items.ReheapUp(0, length-1);
}
}
- Enqueue, Dequeue는 힙의 노드를 추가, 삭제하는 것과 같다.
Graph
-
무방향 그래프
-
방향 그래프
-
그래프 표현
- 인접 행렬
- 메모리 : O((V의 개수)^2)
- 값의 확인이 빠르다. O(1)
- 인접 리스트
- 메모리 : O((V의 개수) + (E의 개수))
- 동적 할당이 가능하다.
- 특정 노드와 인접한 노드를 빠르게 접근할 수 있다.
- 완전 그래프인 경우 각 list 별로 n-1개의 엣지를 가지기 때문에 행렬에 비해 이득이 되지 않는다.
- 인접 행렬
const int NULL_EDGE = 0;
template<class VertexType>
class GraphType {
public:
GraphType(int);
~GraphType();
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void AddVertex(VertexType);
void AddEdge(VertexType, VertexType, int);
int WeightIs(VertexType, VertexType);
void GetAdjacents(VertexType,QueType<VertexType>&);
void ClearMarks();
void MarkVertex(VertexType);
bool IsMarked(VertexType) const;
private:
int numVertices;
int maxVertices;
VertexType* vertices;
int **edges; // 이중 포인터 -> 행렬
bool* marks;
};
template<class VertexType>
GraphType<VertexType>::GraphType(int maxV){
numVertices = 0;
maxVertices = maxV;
vertices = new VertexType[maxV];
edges = new int[maxV]; // 배열을 동적 할당 받는다.
for(int i = 0; i < maxV; i++)
edges[i] = new int[maxV];
marks = new bool[maxV];
}
template<class VertexType>
GraphType<VertexType>::~GraphType(){
delete [] vertices;
for(int i = 0; i < maxVertices; i++)
delete [] edges[i];
delete [] edges;
delete [] marks;
}
void GraphType<VertexType>::AddVertex(VertexType vertex){
vertices[numVertices] = vertex; // 이름 모음에 추가
for(int index = 0; index < numVertices; index++) {
// 엣지 가중치에 NULL값 추가
edges[numVertices][index] = NULL_EDGE;
edges[index][numVertices] = NULL_EDGE;
}
numVertices++;
}
template<class VertexType>
void GraphType<VertexType>::AddEdge(VertexType fromVertex,
VertexType toVertex, int weight){
int row;
int column;
row = IndexIs(vertices, fromVertex);
col = IndexIs(vertices, toVertex);
edges[row][col] = weight;
}
template<class VertexType>
int IndexIs(VertexType* vertices, VertexType vertex)
{
int index = 0;
while (!(vertex == vertices[index]))
index++;
return index;
}
template<class VertexType>
int GraphType<VertexType>::WeightIs(VertexType fromVertex,
VertexType toVertex){
int row;
int column;
row = IndexIs(vertices, fromVertex);
col = IndexIs(vertices, toVertex);
return edges[row][col];
}
Searching
- DFS(Depth First Search) - 깊이 우선 탐색. 스택으로 구현된다.
template<class VertexType>
void GraphType<VertexType>::GetAdjacents(VertexType vertex,
QueTye<VertexType>& adjvertexQ){
int fromIndex;
int toIndex;
fromIndex = IndexIs(vertices, vertex);
for(toIndex = 0; toIndex < numVertices; toIndex++)
if(edges[fromIndex][toIndex] != NULL_EDGE)
adjvertexQ.Enqueue(vertices[toIndex]);
}
template <class ItemType>
void DepthFirstSearch(GraphType<VertexType> graph,
VertexType startVertex, VertexType endVertex)
{
StackType<VertexType> stack;
QueType<VertexType> vertexQ;
bool found = false;
VertexType vertex;
VertexType item;
graph.ClearMarks();
stack.Push(startVertex);
do {
stack.Pop(vertex);
if(vertex == endVertex)
found = true;
else {
if(!graph.IsMarked(vertex)) {
graph.MarkVertex(vertex);
graph.GetAdjacents(vertex, vertexQ);
while(!vertexQ.IsEmpty()) {
vertexQ.Dequeue(item);
if(!graph.IsMarked(item))
stack.Push(item);
}
}
} while(!stack.IsEmpty() && !found);
if(!found)
cout << "Path not found" << endl;
}
- BFS(Breadth First Search) - 너비 우선 탐색. 큐로 구현된다.
template<class VertexType>
void BreadthFirtsSearch(GraphType<VertexType> graph,
VertexType startVertex, VertexType endVertex);{
QueType<VertexType> queue;
QueType<VertexType> vertexQ;//
bool found = false;
VertexType vertex;
VertexType item;
graph.ClearMarks();
queue.Enqueue(startVertex);
do {
queue.Dequeue(vertex);
if(vertex == endVertex)
found = true;
else {
if(!graph.IsMarked(vertex)) {
graph.MarkVertex(vertex);
graph.GetAdjacents(vertex, vertexQ);
while(!vertxQ.IsEmpty()) {
vertexQ.Dequeue(item);
if(!graph.IsMarked(item))
queue.Enqueue(item);
}
}
}
} while (!queue.IsEmpty() && !found);
if(!found)
cout << "Path not found" << endl;
}