Priority Queue Using Heap
#include “Event.cpp”
#include “Heap.cpp”
#define PQMAX 30
class PriorityQueue
{
public:
PriorityQueue() {
heap = new Heap<Event>( PQMAX );
};
~PriorityQueue() {
delete heap;
};
Lecture No.33
Data Structure
Dr. Sohail Aslam
Priority Queue Using Heap
Event* remove()
{
if( !heap->isEmpty() ) {
Event* e;
heap->deleteMin( e );
return e;
}
return (Event*)NULL;
cout << "remove - queue is empty." << endl;
};
Priority Queue Using Heap
int insert(Event* e)
{
if( !heap->isFull() ) {
heap->insert( e );
return 1;
}
cout << "insert queue is full." << endl;
return 0;
};
int full(void){
return heap->isFull();
};
int length() { return heap->getSize(); };
};
The Selection Problem
Given a list of N elements (numbers,
names etc.), which can be totally ordered,
and an integer k, find the kth smallest (or
largest) element.
One way is to put these N elements in an
array an sort it. The kth smallest of these is
at the kth position.
