#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; }
Copyrights © - Joinc, All Rights Reserved. Inherited From - Yundream Rebranded By - Joonphil
Recent Posts
Archive Posts
Tags