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