CLOSE

Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

queue(:12)자료구조를 사용해서, 입력된 숫자를 정렬하는 코드입니다. Template를 써서 일반화 시킬수 있을 겁니다.
```#include <stdio.h>
#include <vector>
#include <list>
#include <iostream>
#include <set>
#include <time.h>
#include <unistd.h>
#include <sys/time.h>

using namespace std;

const int FAULT = 1<<31;

// Random 값 생성기
vector<int> MakeRandomInt(int num, int maxrange)
{
set<int> did;
vector<int> rtv;
int i = 0;
int rnum;

while(i < num)
{
rnum = random()%maxrange;
if(did.find(rnum) == did.end())
{
did.insert(rnum);
rtv.push_back(rnum);
i++;
}
}
return rtv;
}

class PriorityQueue
{
private:
int maxsize;
int size;
int max;
int *heap;
int faluse;
public:
PriorityQueue(int csize)
{
maxsize = csize;
size = 0;
heap = (int *)malloc(sizeof(int) * (maxsize+4));
}
void Print()
{
printf("Show =========\n");
for (int i = 0; i < size; i++)
{
printf("%d\n", heap[i+1]);
}
}
int top()
{
if (size > 0)
return heap[1];
else
return FAULT;
}
void Insert(int a)
{
if (size < maxsize)
{
put(a);
}
else if (size > 0 && !(a < top()))
{
heap[1] = a;
downHeap();
}
}

void put(int a)
{
size++;
heap[size] = a;
upHeap();
}

void upHeap()
{
int i = size;
int node = heap[i];
int j = i >> 1;
j = j & ~(1 << 31) ;
while((j > 0) && (node < heap[j]))
{
heap[i] = heap[j];
i = j;
j = j >> 1;
j = j & ~(1 << 31);
}
heap[i] = node;
}

int pop()
{
if (size > 0)
{
int result = heap[1];
heap[1] = heap[size];
heap[size] = FAULT;
size --;
downHeap();
return result;
}
else
{
return FAULT;
}
}

int Size()
{
return size;
}

void downHeap()
{
int i = 1;
int node = heap[i];
int j = i << 1;
int k = j + 1;
if ( k <= size && (heap[k] < heap[j]))
{
j = k;
}
while((j <= size) && (heap[j] < node))
{
heap[i] = heap[j];
i = j;
j = i << 1;
k = j + 1;
if ((k <= size) && (heap[k] < heap[j]) )
{
j = k;
}
}
heap[i] = node;
}
};

int main(int argc, char **argv)
{
int i;
vector<int> value;
vector<int> pqueue(20);
value = MakeRandomInt(100, 1000);
PriorityQueue PQueue(10);
for (i = 0; i < value.size(); i++)
{
PQueue.Insert(value[i]);
}
PQueue.Print();
return 0;
}```