I am trying to implement something like this to sort my linked list in descending order (I think), cause I am storing the list in a queue and when I delete them I want to print them as they dequeue and they should print in ascending order. My problem is implementing this sort into my existing code which uses a few header files and template classes. I get really confused when using template classes.... I guess I am trying to create a sorting function or functions that can be implemented into a linkedlist header file and called from the priority queue(main) header file.I needed to show an implementation using both a heap and a linked list. I got the heap implementation working. Here is heap header file showing how I am reordering the data in the heap:

#ifndef HEAP_H

#define HEAP_H

template

void swapHeapDown(T& one, T& two, int& count);

template

void swapHeapUp(T& one, T& two, int& count);

template

struct Heap

{

void ReheapDown(int root, int bottom);

void ReheapUp(int root, int bottom);

T* element;

int enqueCount;

int dequeCount;

};

template

void swapHeapDown(T& first, T& second, int& count)

{

T temp;

count++;

temp = first;

count++;

first = second;

count++;

second = temp;

}

template

void swapHeapUp(T& first, T& second, int& count)

{

T temp;

count++;

temp = first;

count++;

first = second;

count++;

second = temp;

}

template

void Heap::ReheapUp(int root, int bottom)

{

int parent;

if (bottom > root)

{

parent = (bottom - 1) / 2;

enqueCount++;

if (element[parent] > element[bottom])

{

swapHeapUp(element[parent], element[bottom], enqueCount);

ReheapUp(root, parent);

}

}

}

template

void Heap::ReheapDown(int root, int bottom)

{

int minChild;

int rightChild;

int leftChild;

leftChild = root * 2 + 1;

rightChild = root * 2 + 2;

if (leftChild <= bottom)

{

if(leftChild == bottom)

{

minChild = leftChild;

}

else

{

dequeCount++;

if (element[leftChild] >= element[rightChild])

{

minChild = rightChild;

}

else

{

minChild = leftChild;

}

}

dequeCount++;

if (element[root] > element[minChild])

{

swapHeapUp(element[root], element[minChild], dequeCount);

ReheapDown(minChild, bottom);

}

}

}

#endif

Here is snippet from my main header file: Showing where I am calling the heap ordering functions and where I need to implement a linkedlist ordering call function.

//**************************************************************************************

// Dequeue

//

//

//**************************************************************************************

template

void PriorityQueue::Dequeue(T& item)

{

if (length == 0)

{

throw EmptyPQ();

}

else

{

item = items.element[0];

items.element[0] = items.element[length - 1];

length--;

items.ReheapDown(0, length - 1);

}

}

//**************************************************************************************

// Enqueue

//

//

//**************************************************************************************

template

void PriorityQueue::Enqueue(T newItem)

{

if (length == maxItems)

{

throw FullPQ();

}

else

{

length++;

items.element[length - 1] = newItem;

items.ReheapUp(0, length - 1);

}

}

//**************************************************************************************

// AddToQueueList

//

//

//**************************************************************************************

template

void PriorityQueue::AddToQueueList(T newItem)

{

if (ListLength == maxItems)

{

cout << " Queue is Full! ";

system("pause");

}

else

{

NodeType* newNode;

newNode = new NodeType;

newNode->info = newItem;

newNode->next = NULL;

if (rear == NULL)

{

front = newNode;

}

else

{

rear->next = newNode;

}

rear = newNode;

ListLength++;

}

}

//**************************************************************************************

// RemoveFromQueueList

//

//

//**************************************************************************************

template

void PriorityQueue::RemoveFromQueueList(T& item)

{

if (ListLength == 0)

{

cout << " Queue is empty! ";

//system("pause");

}

else

{

NodeType* tempPtr;

tempPtr = front;

item = front->info;

front = front->next;

if (front == NULL)

{

rear = NULL;

}

delete tempPtr;

ListLength--;

cout << item << " ";

//system("pause");

}

}