yundream의 답변

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