[21.08.27]Priority_queue / Heap Sort / Dijkstra알고리즘

- STL 사용하지않고 구현하기

#include<iostream>
using namespace std;
int heap[30];
int index;
void push(int value)
{
    // 1 번 인덱스 부터
    heap[++index] = value;      

// 부모 그리고 넘어온 값
int p, now; 
now = index;

while (1)
{
    // 부모 인덱스 확인
    p = now / 2;

    // 1번 인덱스만 체워짐
    if (now == 1)break;

    // 부모랑 들어온 값이랑 비교후 스왑
    if (heap[p] > heap[now])swap(heap[p], heap[now]);
    else break;

    // 부모를 기점으로 더 위(부모의 부모랑 비교)
    now = p;
}
}

int top()
{
    return heap[1];
}

void pop()
{
    // 맨 끝을 맨 위로 올리고
    heap[1] = heap[index];

//맨 끝값을 지우고
heap[index] = 0;
index--;


int p, son, son2;
p = 1;

while (1) {

    son = p * 2;  // 왼쪽자식
    son2 = son + 1;  // 오른쪽 자식

    // 오른쪽에 자식이 있고 자식들 비교해서 작은 자식을 = son
    if (son2 <= index && heap[son] > heap[son2])son = son2;

    //  배열에 마지막만 남거나 부모가 자식보다 작으면 break
    if (son > index || heap[p] < heap[son])break;
    else swap(heap[p], heap[son]);

    // 트리의 밑을 보기 (자식이 다시 부모가 되어서 체크)
    p = son;
}
}

int main()
{
    push(9);
    push(3);
    push(5);
    push(2);
    push(8);
    push(4);
    push(1);

for (int x = 0; x < 7; x++)
{
    cout << top() << " ";
    pop();
}

return 0;
}

- STL 사용하기

#include<iostream>
#include<queue>

using namespace std;

priority_queue<int,vector<int>,greater<int>>q; //오름차순
//priority_queue<int,vector<int>,less<int>>q; //max heap(내림차순)일경우 생략가능

int main() {
    q.push(4);
    q.push(14);
    q.push(44);
    q.push(64);
    q.push(43);
    q.push(24);

    int len = q.size();

    for (int i = 0; i < len; i++) {
        cout << q.top() << " ";
        q.pop();
    }

    return 0;
}

- operator 사용하기(우선순위 - 숫자 오름차순, 문자오름차순)

#include<iostream>
#include<queue>

using namespace std;

struct node {
    int num;
    char ch;
};

node vect[7] = {
    {3,'b'},
    {1,'k'},
    {5,'b'},
    {13,'a'},
    {1,'c'},
    {3,'a'},
    {1,'d'}
};

priority_queue<node>q;

// 첫번째 인자값의 우선순위가 더 낮다면 true를 반환
// sort랑 반대 주의!
bool operator<(node back, node front) {
    if (front.num < back.num) return true;
    if (front.num > back.num) return false;

    return front.ch < back.ch;

}

int main() {
    for (int x = 0; x < 7; x++) {
        q.push(vect[x]);
    }

    for (int x = 0; x < 7; x++) {
        cout << q.top().num << " " << q.top().ch << endl;
        q.pop();
    }

    return 0;
}

- 2차원배열의 값 큰것부터 위치 출력하기

#include<iostream>
#include<queue>

using namespace std;

struct node {
    int y, x;
    int num;
};

int map[3][3] = {
    4,7,3,
    1,94,5,
    6,2,8
};

priority_queue<node>q;

bool operator<(node back, node front) {
    return front.num < back.num;
}

int main() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            q.push({ i,j,map[i][j] });
        }
    }

    for (int i = 0; i < 9; i++) {
        cout << q.top().y << " " << q.top().x << endl;
        q.pop();
    }

    return 0;
}

- *2, *3, *5 로 구현가능한 숫자중 n번째 수 찾기

#include<iostream>
#include<queue>
#include<vector>
#include<string>

using namespace std;

priority_queue<int, vector<int>, greater<int>>q;

vector<int>vect;

int main() {

    int n;
    cin >> n;

    q.push(1);
    int now;
    int before = 0;

    for (int x = 0; x < n; x++) {

        //중복제거
        while (1) {
            now = q.top();
            q.pop();

            if (now != before)break;
        }
        before = now;

        vect.push_back(now);

        q.push(now * 2);
        q.push(now * 3);
        q.push(now * 5);
    }

    cout << vect[n - 1];
   
    return 0;
}

Heap은 Data를 이진트리 형태로 저장해두고, 우선순위가 높은 값을 빠르게 찾아주는 자료구조 입니다.

---

다익스트라 알고리즘 - 경로가 양수로만 정해져있음( 갈수없는곳은 큰값으로 채움)

#include<iostream> // 다익스트라 n2
using namespace std;
char name[6] = "ABCDE";
const int m = 999;
int map[5][5] = {
    m,3,m,9,5,
    m,m,7,m,1,
    m,m,m,1,m,
    m,m,m,m,m,
    m,m,1,m,m,
};
int result[5] = {
    m,3,m,9,5,
};

int used[5] = { 1 };

int check()
{
    int Min = 21e8;
    int Minindex = 0;
    for (int x = 0; x < 5; x++)
    {
        if (used[x]==0 && result[x] < Min) {
            Min = result[x];
            Minindex = x;
        }
    }
    return Minindex;
 }
void daijk()
{
    for (int y = 0; y < 4; y++)
    {
        int via = check();  //   경유지 선택
        used[via] = 1;

    for (int x = 0; x < 5; x++)
    {
        int baro = result[x];
        int kyoung = result[via] + map[via][x];
        if (baro > kyoung)result[x] = kyoung;

    }

}
}
int main()
{

daijk();
char ends;
cin >> ends;
for (int x = 0; x < 5; x++)
{
    if (name[x] == ends)
    {
        cout << result[x];
        break;
    }
}

return 0;
}

#include<iostream>  //  다익스트라  nlogn

#include<queue>

#include<vector>
using namespace std;
char name[6] = "ABCDE";
struct node {
    int n;  // 인덱스
    int price;
};

vector<vector<node>>vect(5);

priority_queue<node>q;

int result[5] = { 999,999,999,999,999 };

int used[5];

bool operator<(node back, node front) // 우선순위 조건
{
    return front.price < back.price;
}

int main()
{
    // 인접 리스트
    vect[0].push_back({ 1,3 }); 
    vect[0].push_back({ 3,9 }); 
    vect[0].push_back({ 4,5 }); 
    vect[1].push_back({ 2,7 }); 
    vect[1].push_back({ 4,1 }); 
    vect[2].push_back({ 3,1 }); 
    vect[4].push_back({ 2,1 }); 

q.push({ 0,0 });

while (!q.empty())
{
    node via = q.top();
    q.pop();

    if (used[via.n] == 1)continue;
    used[via.n] = 1;

    // result  vs  경유지 거쳐서 가는 비용 비교후   result 갱신

    for (int x = 0; x < vect[via.n].size(); x++)
    {
        node target = vect[via.n][x];

        if (result[target.n] > via.price + target.price) {
            result[target.n] = via.price + target.price;
            q.push({ target.n,result[target.n] });
        }

    }



}


return 0;
}