priority queue

I know queue but with priority queue i am really amateur.
can you help me implement some functions in priority queue. thanks in advance!

template <class T> class PRIORITY_QUEUE {
private:
T *items; // array of queue items
int rear;
int maxSize; // maximum size of queue
void heapify(int i); // adjust heap at position “i”
public:
PRIORITY_QUEUE(int size); // create queue with ‘size’ items
PRIORITY_QUEUE(const PRIORITY_QUEUE &aQueue);
~PRIORITY_QUEUE(); // destructor
bool isEmpty();
void insert(T newItem);
T deleteMin();
};

and what does heapify mean???

nightmaregiba (63)

and what i should know to implement it?

doug4 (453)

Try googling "heapify". That will give you a number of pages that help explain it. Essentially, a heap is a binary tree in which all child nodes of are less than the parent node, and all nodes in the tree. Every sub-tree is a heap. The wikipedia page (http://en.wikipedia.org/wiki/Heapsort) shows to implement this as an array.

nightmaregiba (63)

i understand heapify but how to implement

void heapify(int i); >>>???

doug4 (453)

The pseudo-code on the wikipedia page is actually pretty clear. It is more complete than something I would write up. Read the Overview section (to understand how the tree is represented in the array) and the beginning of the Pseudocode section (for a description of heapsort(), heapify() and siftDown() ). At the end of the Pseudocode section is an alternative method of heapify() using siftUp(). You can use whichever one you want to use. The variable 'count' is the size of the array being heapified. Your PRIORITY_QUEUE class should have that variable available somehow (maybe that's what maxSize is supposed to be?).

BTW, Sorry about the bad link in the previous post. The closing ')' got mixed into the link somehow.

http://en.wikipedia.org/wiki/Heapsort

MikeyBoy (2454)

BTW, Sorry about the bad link in the previous post. The closing ')' got mixed into the link somehow.

FYI, you can avoid that by having a space between the URL and the trailing punctuation (like this: http://en.wikipedia.org/wiki/Heapsort )

It can also happen at the end of the sentence, so a space is needed there too: http://en.wikipedia.org/wiki/Heapsort .

nightmaregiba (63)

thks

nightmaregiba (63)

int rear here mean the position of the last element?

Registered users can post here. Sign in or register to post.