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;
}

🖥️ Techtellus

Explorer

DS-L09

Heap

Priority Queue

Graph

Searching

Graph View

Table of Contents