우선순위큐_배열

#include<iostream>

#include<stdlib.h>

struct priority_queue {

int cost;

}pq[1000],temp;

int pq_count=0;

void pq_pop();

void pq_push(int cost);

bool pq_empty();

void pq_clear();

int main() {

for (int i = 10; i > 0; i--) {

pq_push(i);

}

for (; !pq_empty();) {

pq_pop();

std::cout << " ";

}

std::cout << std::endl;

return 0;

}

void pq_pop() {

//int print_pop = pq[1].cost;

std::cout << pq[1].cost;

pq[1] = pq[pq_count--];

for (int parrent = 1;;) {

int child = parrent * 2;

//e가 전체 노드 수보다 많으면 종료

if (child > pq_count)

return ;

//e와e+1이 전체 노드개수보다 큰지비교후 왼쪽이 큰지 오른쪽이 큰지 비교

if (child + 1 <= pq_count && pq[child].cost > pq[child + 1].cost)

child++;

//부모가 자식보다 크면 바꾼다.

if (pq[parrent].cost > pq[child].cost) {

temp = pq[parrent];

pq[parrent] = pq[child];

pq[child] = temp;

//바꾼 자식의 값을 보려는 기준으로 삼는다

parrent = child;

}else break;

}

}

void pq_push(int cost) {

//맨 마지막에 데이터를 추가

pq[++pq_count].cost = cost;

//맽 밑레벨에서부터 부모로 올라오면서 체크  한번 돌때마다 한칸 위로 올라간다

for (int i = pq_count; i > 1; i /= 2) {

//입력받은 데이터가 바로위 부모보다 작으면

if (cost < pq[i / 2].cost)

//부모의 데이터를 밑으로 내린다.

pq[i] = pq[i / 2];

//계속 올라갔을때 부모의 값이 맨밑보다 작으면 멈추고 

    //현재 위치에 값을 넣는다 그러면 자동으로 정렬이 된다.

else {

pq[i].cost = cost;

return;

}

}

pq[1].cost = cost;

}

bool pq_empty() {

if (pq_count == 0)return true;

else return false;

}

void pq_clear() {

pq_count = 0;

}