자료구조 및 알고리즘 #12 - an Application of Heap and Priority Queue

0. 들어가기 전

 

2024.05.18 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 7 - Heap

자바[JAVA] 자료구조 구현 7 - Heap

위 글을 통해 Heap 에 대한 기본적인 이해가 되었다고 가정하고 진행하겠습니다.

 

1. Priority Queue

 

2024.04.11 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack

자료구조 및 알고리즘 5 - Queue and Stack

에서 설명했듯이 일반적으로 Queue 자료구조는 선입선출(* FIFO) 을 특징으로 하는 자료구조입니다. Priority Queue 도 Queue 자료구조를 기반으로 하기에 비슷합니다. 하지만 일반적인 Queue 와 다른점은 각각의 Item 들이 우선순위를 가지고 있다는 점 입니다.

 

즉, 우선순위가 높은 Item 먼저 나올 수 있습니다. 그런데 이 자료구조가 왜 필요할까요?

 

우리는 앞서 AVL 트리와 같은 다양한 자료구조를 통해 O(logN) 의 시간안에 삽입, 삭제가 가능하다는 것을 봤습니다. 그리고 정렬은 O(NlogN) 의 시간안에 가능합니다.(* N 개의 요소들에 대해 삽입(logN) 이 이루어지면 그대로 정렬이 완성됨)  그런데 이보다 더 빠르게 S, I, D 를 수행할 수 있는것을 상상할 수 있을까요? O(N) 에 정렬이 이루어지는 자료구조..? 상상하기 힘듭니다.

 

어떤 알고리즘을 구현할때면 심심치 않게 나오는 것이 있습니다. 바로 최대값 또는 최솟값 찾기 입니다. 어떤 배열이 있을 때 최소값을 구하는데 걸리는 시간은 얼마일까요? 일반적인 배열이라면 우선 정렬을 수행한 후 최소값을 찾아야 할 것 입니다.

 

우리가 이전에 봤었던 Marge Sort 를 사용한다면 O(NlogN) 에 정렬을 수행하고, Search에 상수시간이 걸리니, O(NlogN) 에 수행할 수 있을 것입니다.

 

우리가 이전에 해봤던 AVL 트리를 사용한다면 삽입하는데에 O(logN), 이를 모든 원소에 대해 해야하니 O(NlogN) 에 수행되고, 검색은 O(logN) 에 수행되므로 AVL 트리 또한 O(NlogN) 에 시간에 수행됩니다.

 

하지만 Priority Queue 는 더 빠릅니다. 같은 O(NlogN) 이지만 더 빠릅니다. 어떻게 그럴 수 있을까요? 방법은 느슨한 규칙에 있습니다.

 

일반적인 BST 와 같은 트리들은 한 번 정렬이 이루어지면 가장 작은 수, 두 번째로 작은 수, ... 등 n 번째로 작은 수를 찾는 것이 가능합니다.

하지만 Priority Queue 는 다릅니다. PQ 는 빠르게 최솟값, 최댓값을 찾을 수 있는 대신 그 다음 수, 즉 다른 나머지 수들이 어디에 있는지는 찾을 수 없습니다.

즉, 최소, 최대값을 제외한 값들이 있을 수 있는 위치가 다른 자료구조들에 비해 자유롭다는 의미이고, 이는 수행시간의 단축으로 이어집니다.

 

바로 PQ 를 만드는 자료구조가 Heap 입니다. 앞서 Heap 이 어떤 자료구조인지 살펴봤기 때문에 바로 PQ 의 Application 으로 넘어가겠습니다.

 

2. Dijkstra Algorithm

 

다익스트라 알고리즘은 가중치가 있는 그래프에 대해서 특정 노드 n 에서 시작하여 각 노드까지 도달하는 최단 거리를 찾는 알고리즘입니다. 자세한 알고리즘에 대한 설명은 나중에 하고 해당 알고리즘에서 어떻게 PQ 가 사용되는지만 빠르게 살펴보겠습니다.

 

다익스트라 알고리즘에서 가장 중요한 부분은 이미 최단 거리가 알려진 노드들(A)과 연결된 노드들(B) 에 대한 거리들 중 가장 짧은 거리의 노드를 찾는 것입니다.

 

만약 PQ 를 사용하지 않고 최소값을 찾는다면(* 선형으로 탐색하며 최소값을 찾는다면) 총 소요시간은 O(N^2) 이 소요됩니다. 하지만 PQ 를 통해 최소값을 찾는데에 걸리는 시간을 단축한다면 총 소요시간은 O(NlogN) 에 가능합니다.

 

(* 단 이때의 PQ 는 일반적인 PQ 로는 메모리 낭비가 심하다는 부작용이 있습니다. 그래서 decrease_key 기능을 갖는 PQ 인 피보나치 힙을 사용한다면 메모리 부담 없이 O(NlogN) 에 수행할 수 있습니다.)

 

다익스트라 알고리즘의 수행은 다음과 같습니다.

1. 출발 노드와 도착 노드를 설정한다.
2. '최단 거리 테이블'을 초기화한다. (* 이때 최단 거리 테이블이란, 출발 노드에서부터 모든 노드에 도달하는데 걸리는 거리의 최단거리들을 적어놓은 테이블입니다. 이 테이블이 다익스트라 알고리즘의 결과가 됩니다.)
3. 현재 위치한 노드의 인접 노드들 중 방문하지 않는 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를선택한다. 그 후 그 노드를 방문 처리한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다.
5. 3~4 의 과정을 반복한다. 

// heap and Djikstra

/*
INPUT
6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
*/

class Node {
public:
    int key;
    std::vector<Node*> adj;
    int weight;

    Node(int x, int w) {
        key = x;
        weight = w;
    }
    Node(int x) {
        key = x;
        weight = 0;
    }
    Node() {
        key = 0;
        weight = 0;
    }
    // Heap 에서의 빠른 비교를 위한 operator 오버라이딩
    bool operator < (Node& n) {
        return this->weight < n.weight;
    }
    // 인접리스트에 노드를 추가하는 메서드
    void add(Node* n) {
        adj.push_back(n);
    }
};

// 보다 빠른 Djikstra 알고리즘을 위한 Heap
class Heap {
public:
    Node** heap = new Node * [1001];
    int count = 0;
    // Heap 의 최대사이즈
    // 해당 코드에는 최대사이즈에 관한 예외처리는 하지 않았다.
    const int MAX_SIZE = 1000;

    void Insert(Node* n);
    void Delete();
    Node* Top();
};

void Heap::Insert(Node* n) {
    if (count == 0) {
        heap[++count] = n;
    }
    else {
        int idx = ++count;
        heap[idx] = n;
        while (idx > 1) {
            int parentIdx = idx / 2;
            if (*heap[parentIdx] < *heap[idx]) {
                break;
            }
            else {
                // swap
                Node* temp = heap[parentIdx];
                heap[parentIdx] = heap[idx];
                heap[idx] = temp;

                // heap up
                idx = parentIdx;
            }
        }
    }
}

void Heap::Delete() {
    if (count == 0) {
        std::cout << "there is no element" << std::endl;
    }
    else {
        int idx = 1;
        heap[idx] = heap[count--];
        while (true) {
        	// 자식 노드가 아에 없는 경우
            if (idx * 2 > count) {
                break;
            }
            // 왼쪽 자식 노드만 있는 경우
            else if (idx * 2 == count) {
                int childIdx = idx * 2;
                if (*heap[childIdx] < *heap[idx]) {
                    // swap
                    Node* temp = heap[childIdx];
                    heap[childIdx] = heap[idx];
                    heap[idx] = temp;

                    // heap down
                    idx = childIdx;
                }
                // 더 이상 내려갈 수 없으니 그냥 break
                break;
            }
            // 자식 노드가 2개 있는 경우
            else {
            	// 자식 노드들 중 우선순위가 높은 노드 찾기
                int smallestIdx = *heap[idx * 2] < *heap[idx * 2 + 1] ? idx * 2 : idx * 2 + 1;
                if (*heap[smallestIdx] < *heap[idx]) {
                    //swap
                    Node* temp = heap[smallestIdx];
                    heap[smallestIdx] = heap[idx];
                    heap[idx] = temp;

                    // heap down
                    idx = smallestIdx;
                }
            }
        }
    }
}

Node* Heap::Top() {
    return heap[1];
}

void Dijkstra() {
    int N; // N is # of nodes
    int M; // M is # of edges or relations

    std::cin >> N;
    std::cin >> M;

    Heap heap;
    Node** nodeList = new Node * [N + 1];
    // nodeList 초기화
    for (int i = 1; i < N + 1; i++) {
        nodeList[i] = new Node(i);
    }
    for (int i = 0; i < M; i++) {
        int v1;
        int v2;
        int weight;

        std::cin >> v1;
        std::cin >> v2;
        std::cin >> weight;

        nodeList[v1]->add(new Node(v2, weight));
    }

    int* resultList = new int[N + 1]; // distance list from node # 1
    resultList[1] = 0; // distance from 1 to 1 is 0
    for (int i = 2; i < N + 1; i++) {
    	// 1 -> 1 을 제외한 노드들의 거리는 Inf
        resultList[i] = INT_MAX;
    }

    Node* startNode = nodeList[1];
    // 사실 반복을 unvisited set 이 empty 일 때까지 하는건데
    // set 을 사용하지 않고 그냥 N 번만 수행하는것으로 함
    // 만약 N 번 안에 도달하지 못하는 노드는 그냥 연결되지 않은 노드로 판단
    for (int i = 0; i < N; i++) {
        for (auto it = startNode->adj.begin(); it != startNode->adj.end(); it++) {
            Node* adjNode = *it;
            if (resultList[adjNode->key] > resultList[startNode->key] + adjNode->weight) {
                heap.Insert(new Node(adjNode->key, resultList[startNode->key] + adjNode->weight));
                resultList[adjNode->key] = resultList[startNode->key] + adjNode->weight;
            }
        }
        // Heap 을 이용해 거리가 가장 작은 노드를 찾아서
        // 다음 노드로 설정
        startNode = nodeList[heap.Top()->key];
        heap.Delete();
    }

    for (int i = 1; i < N + 1; i++) {
    	// 만약 결과 리스트의 값이 Inf 면 그냥 path 가 없는것임 
        if (resultList[i] == INT_MAX) {
            std::cout << "There is no path from node # 1 to node # " << i << std::endl;
        }
        else {
            std::cout << "Distantce from node # 1 to node # " << i << " is " << resultList[i] << std::endl;
        }
    }
}

int main(){
	Djikstra();
    return 0;
}

 

 

3. Heap sort

 

힙 정렬은 병합 정렬(* Marge Sort) 와 같이 굉장히 빠른 시간안에 정렬을 수행해주는 정렬 알고리즘 중 하나입니다. 힙 정렬은 말 그대로 Heap 자료구조를 이용하여 정렬을 수행하는 알고리즘으로 N 개의 요소들을 일단 Heap 에 넣고, 빼기만 하면 정렬이 됩니다.