• queue(12)를 list가 아닌 일반 배열로 구현했음
  
• queue는 TopN이 보장되지만 완전정렬이 되지는 않음
  

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