priority queue

[nightmaregiba]

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]

and what i should know to implement it?

[doug4]

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]

i understand heapify but how to implement

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

[doug4]

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]

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]

thks

[nightmaregiba]

int rear here mean the position of the last element?

[doug4]

In the heapsort function (on the wiki page) there is a value called end. After the array is heapified, the largest value in the array is located at a[0], but none of the other values is guaranteed. The array is sorted from smallest to largest by taking the largest value (always located at a[0]) and moving it to the end of the unsorted values (a[end]). The largest value is swapped with a[end], and that value is sifted down to restore the heap such that the largest remaining value is at a[0]. The algorithm loops through each element in the array, each time decrementing the end value to represent where the unsorted values reside. The loops continue until the entire array is sorted.

The end value in the wiki page is equivalent to the rear value in your sample code above.