C++

Forum

 
Heap Priority Queue for to-do list

Pages: 12
Lacy9265 (119)
1st part of ArrayMaxHeap.h file 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
#ifndef ARRAY_MAX_HEAP_
#define ARRAY_MAX_HEAP_

#include "HeapInterface.h"
#include "PrecondViolatedExcept.h"
#include <math.h>
#include <stdio.h>



template<class ItemType>
class ArrayMaxHeap : public HeapInterface<ItemType>
{
private:
	static const int ROOT_INDEX = 0; // Helps with readibility 
	static const int DEFAULT_CAPACITY = 21; 
	ItemType* items; // Array of heap items
	int itemCount; // Current count of heap items 
	int maxItems; // Max capcity of the heap

	// Returns the array index of the left child
	int getLeftChildIndex(const int nodeIndex) const;

	// Returns the array index of the right child
	int getRightChildIndex(int nodeIndex) const;

	// Returns the array index of the parent node
	int getParentIndex(int nodeIndex) const;

	// Tests whether this node is a leaf
	bool isLeaf(int nodeIndex) const;

	// Converts the semiheap to a heap
	void heapRebuild(int nodeIndex);

	// Creates a heap from from unordered array
	void heapCreate();

public:
	ArrayMaxHeap();
	ArrayMaxHeap(const ItemType someArray[], const int arraySize);
	virtual ~ArrayMaxHeap();


	bool isEmpty() const;
	int getNumberOfNodes() const;
	int getHeight() const;
	ItemType peekTop() const throw(PrecondViolatedExcep);
	bool add(const ItemType& newData);
	bool remove();
	void clear();
};
// -------------------------------------------------------------------
// getLeftChildIndex: Returns the array index of the left child
// nodeIdex: is the index of the node
// returns the left node index
// -------------------------------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getLeftChildIndex(const int nodeIndex) const
{
    return (2 * nodeIndex) + 1;
}


// ----------------------------------------------------------------------
// getRightChildIndex: Returns the array index of the right child
// nodeIndex: is the index of the right node
// return the right node index
// ----------------------------------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getRightChildIndex(const int nodeIndex) const
{
    return (2 * nodeIndex) + 2;
}


// -------------------------------------------------------------------
// getParentIndex: Returns the parent node index
// nodeIndex: is the index of the parent node
// returns the array index of the parent node
// -------------------------------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getParentIndex(const int nodeIndex) const
{
    return (nodeIndex - 1) / 2;
}

//-------------------------------------------------------------
// isLeaf: Tells us if the node is a leaf
// nodeIdex: is the index of a node
// returns the left child index method
// ------------------------------------------------------------
template<class ItemType>
bool ArrayMaxHeap<ItemType>::isLeaf(const int nodeIndex) const
{
    return (getLeftChildIndex(nodeIndex) >= itemCount);
}
Lacy9265 (119)
2nd part of ArrayMaxHeap.h file 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
//-------------------------------------------------------------------
// heapRebuild: Converts the semi-heap to a heap
// subTreeNodeIndex: the sub-tree array node index
// ------------------------------------------------------------------
template<class ItemType>
void ArrayMaxHeap<ItemType>::heapRebuild(const int subTreeNodeIndex)
{
    // if the node is not a leaf
    if (!isLeaf(subTreeNodeIndex))
    {   
        // Get the left and right child index
        int leftChildIndex = getLeftChildIndex(subTreeNodeIndex);
        int largerChildIndex = leftChildIndex;
        int rightChildIndex = getRightChildIndex(subTreeNodeIndex);
        if (rightChildIndex < itemCount)
        {
            // if the right child index is greater than largest child index
            if (items[rightChildIndex].priorityValue > items[largerChildIndex].priorityValue)
                largerChildIndex = rightChildIndex; // set largest child index to right child index
        }

        // if the sub tree node is less than largest child index
        if (items[subTreeNodeIndex].priorityValue < items[largerChildIndex].priorityValue)
        {
            std::swap(items[largerChildIndex], items[subTreeNodeIndex]); // swap the large child index and sub tree node
            heapRebuild(largerChildIndex); // call on the heapRebuild method
        }
    }
}

// -------------------------------------------------
// heapCreate: creates a heap from an unsorted array
// ------------------------------------------------
template<class ItemType>
void ArrayMaxHeap<ItemType>::heapCreate()
{
    // Create a heap from unsorted array 
    for (int index = itemCount / 2; index >= 0; index--)
    {
        heapRebuild(index); // call on the rebuild method 
    }
}


// ---------------------------------------------------------------------------
// ArrayMaxHeap: sets the number of items to the max capacity
//-----------------------------------------------------------------------------
template<class ItemType>
ArrayMaxHeap<ItemType>::ArrayMaxHeap() :itemCount(0), maxItems(DEFAULT_CAPACITY)
{
    items = new ItemType[DEFAULT_CAPACITY];
}

// -------------------------------------------------------------------------------------
// ArrayMaxHeap: Allocats memory for the array and copy values
// someArray[]: an array of ItemType
// arraySize: the size of the array ItemType
// -------------------------------------------------------------------------------------
template<class ItemType>
ArrayMaxHeap<ItemType>::ArrayMaxHeap(const ItemType someArray[], const int arraySize) :
    itemCount(arraySize), maxItems(2 * arraySize)
{

    // Allocate the array
    items = new ItemType[2 * arraySize];

    // Copy the given values into the array
    for (int i = 0; i < itemCount; i++)
        items[i] = someArray[i];

    // Reorganize the array into the heap
    heapCreate();
}

// -----------------------------------------
// ~ArrayMaxHeap: delete the items of array
// -----------------------------------------
template<class ItemType>
ArrayMaxHeap<ItemType>::~ArrayMaxHeap()
{
    delete[] items; // delete array of items 
}


// ----------------------------------------------
// isEmpty: see if array is empty
// return itemCount when zero
// ----------------------------------------------
template<class ItemType>
bool ArrayMaxHeap<ItemType>::isEmpty() const
{
    return itemCount == 0;
}

// ----------------------------------------------
// getHeight: gets the height of the node
// returns the height of the nodes
// --------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getHeight() const
{
    // Calculate the height
    double y = log(itemCount + 1) / log(2);
    return ceil(y);
}


// --------------------------------------------------
// getNumberOfNodes: gets the number of nodes
// returns the number of nodes
// ---------------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getNumberOfNodes() const
{
    return itemCount;
}

// --------------------------------------
// clear: removes all data from the heap
// --------------------------------------
template<class ItemType>
void ArrayMaxHeap<ItemType>::clear()
{
    itemCount = 0;
}


// ---------------------------------------------------------
//peekTop: Gets the data that is in the top of this heap
// returns the the top of the heap
// ----------------------------------------------------------
template<class ItemType>
ItemType ArrayMaxHeap<ItemType>::peekTop() const throw(PrecondViolatedExcep)
{
    // If the heap is empty throw error
    if (isEmpty())
        throw PrecondViolatedExcep("Attempted peek into an empty heap.");
    return items[0];
}

// ------------------------------------------------------
// add: add values to the heap
// newData: the new data to be added to heap
// returns if adding the new data was successful
// -------------------------------------------------------
template<class ItemType>
bool ArrayMaxHeap<ItemType>::add(const ItemType& newData)
{
    bool isSuccessful = false;

    // if itemCount is less than max items
    if (itemCount < maxItems)
    {
        items[itemCount] = newData;
        bool inPlace = false;
        int newDataIndex = itemCount;

        // While the new data index is greater than zero and not in place
        while ((newDataIndex > 0) && !inPlace)
        {
            int parentIndex = getParentIndex(newDataIndex);

            // If new dtata index is less than parent index 
            if (items[newDataIndex].priorityValue < items[parentIndex].priorityValue)
            {
                inPlace = true; // set inPlace to true 
            }
            else
            {
                std::swap(items[newDataIndex], items[parentIndex]); // swap the index 
                newDataIndex = parentIndex; // set new data index to parent index 
            }
        }
        itemCount++; // count number of items 
        bool isSuccessful = true;
    }
    return isSuccessful; 
}

// ------------------------------------
// remove: remove data from the heap
// returns if the removal was successful
// ------------------------------------
template<class ItemType>
bool ArrayMaxHeap<ItemType>::remove()
{
    bool isSuccessful = false;

    // if the heap is not empty
    if (!isEmpty())
    {
        items[ROOT_INDEX] = items[itemCount - 1];
        itemCount--;
        heapRebuild(ROOT_INDEX);
        bool isSuccessful = true;
    }
    return isSuccessful;
}



#endif
Lacy9265 (119)


Have changed it so the HeapPriorityQueue h and cpp both include eachother. However, still getting the same LNK2019 error I got above.
Last edited on
seeplus (6597)
No. HeapPriorityQueue.cpp must'nt be set as a compilation unit. HeapPriorityQueue.h includes HeapPriorityQuere.cpp at the end (as Is aid above). HeapPriorityQueue.cpp doesn't include HeapPriorityQueue.h

When I get some time in the next couple of hours, I'll rework the code

ArrayMaxHeap.h also has the function implementations in the same file as the class definition. You should do the same for HeapPriorityQueue.h and then you don't need HeapPriorityQueue.cpp
seeplus (6597)
What is common.h?

OK. Found it.
Last edited on
seeplus (6597)
Ok. I've now got it all to compile - but haven't run it. The ONLY compilation unit you use is driver.cpp

HeapPriorityQueue.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#ifndef HEAP_PRIORITY_QUEUE_
#define HEAP_PRIORITY_QUEUE_

#include <iostream>
#include "ArrayMaxHeap.h"
#include "PriorityQueueInterface.h"
#include "PrecondViolatedExcept.h"

template<class ItemType>
class HeapPriorityQueue : public PriorityQueueInterface<ItemType>,
	private ArrayMaxHeap<ItemType>
{
public:
	HeapPriorityQueue();
	bool isEmpty() const;
	bool enqueue(const ItemType& newEntry);
	bool dequeue();
	ItemType peekFront() const; // throw(PrecondViolatedExcep);

	bool add(const ItemType& newEntry) override { return false; }
	bool remove() override { return false; }
	ItemType peek() const override { return {}; }

};

#include "HeapPriorityQueue.cpp"
#endif


HeapPriorityQueue.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
//heappriorityqueue.cpp

template<class ItemType>
inline HeapPriorityQueue<ItemType>::HeapPriorityQueue()
{
    ArrayMaxHeap<ItemType>();
}
template<class ItemType>
inline bool HeapPriorityQueue<ItemType>::isEmpty() const
{
    return ArrayMaxHeap<ItemType>::isEmpty();
}
template<class ItemType>
inline bool HeapPriorityQueue<ItemType>::enqueue(const ItemType& newEntry)
{
    return ArrayMaxHeap<ItemType>::add(newEntry);
}
template<class ItemType>
inline bool HeapPriorityQueue<ItemType>::dequeue()
{
    return ArrayMaxHeap<ItemType>::remove();
}
template<class ItemType>
inline ItemType HeapPriorityQueue<ItemType>::peekFront() const //throw(PrecondViolatedExcep)
{
    try
    {
        return ArrayMaxHeap<ItemType>::peekTop();
    }
    catch (PrecondViolatedExcep e)
    {
        throw PrecondViolatedExcep("Attempted peek into an empty priority queue.");
    }
}


PrecondViolatedExcept.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
/ PrecondViolatedException.h
#ifndef PRECOND_VIOLATED_EXCEP_
#define PRECOND_VIOLATED_EXCEP_

#include <stdexcept>
#include <string>

class PrecondViolatedExcep : public std::logic_error
{
public:
	PrecondViolatedExcep(const std::string& message = "")
		: std::logic_error("Precondition Violated Exception: " + message)
	{
	}
}; // end PrecondViolatedExcep
#endif


common.h 
1
2
3
4
5
6
7
8
9
10
11
 
/ Common.h
#ifndef COMMON_H
#define COMMON_H
#include <string>

struct item
{
    int priorityValue;
    std::string task;
};
#endif



seeplus (6597)
PriorityQueueInterface.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
//PriorityQueueInterface.h
#ifndef PRIORITY_QUEUE_INTERFACE_
#define PRIORITY_QUEUE_INTERFACE_

template<class ItemType>
class PriorityQueueInterface
{
public:
	virtual bool isEmpty() const = 0;
	virtual bool add(const ItemType& newEntry) = 0;
	virtual bool remove() = 0;
	virtual ItemType peek() const = 0;
};
#endif


HeapInterface.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
/HeapInterface.h
#ifndef HEAP_iNTERFACE_
#define HEAP_INTERFACE_

#include <iostream>

template<class ItemType>
class HeapInterface
{
public:
	// See if the heap is empty
	virtual bool isEmpty() const = 0;

	// Gets the number of nodes in this heap
	virtual int getNumberOfNodes() const = 0;

	// Gets the height of the nodes
	virtual int getHeight() const = 0;

	// Gets the data that is in the top of this heap
	// For the maxHeap the data is the largest value in the heap
	// For the minHeap the data is the smmallest value in the heap
	virtual ItemType peekTop() const = 0;

	// Adds new data to the heap
	virtual bool add(const ItemType& newData) = 0;

	// Removes the data that is at the top of the heap
	virtual bool remove() = 0;

	// Removes all data from the heap
	virtual void clear() = 0;

	// Destroys this heap and frees its assigned memory
	virtual ~HeapInterface() { }
};
#endif


seeplus (6597)
ArrayMaxHeap.h (1) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
#ifndef ARRAY_MAX_HEAP_
#define ARRAY_MAX_HEAP_

#include "HeapInterface.h"
#include "PrecondViolatedExcept.h"
#include <math.h>
#include <stdio.h>



template<class ItemType>
class ArrayMaxHeap : public HeapInterface<ItemType>
{
private:
	static const int ROOT_INDEX = 0; // Helps with readibility
	static const int DEFAULT_CAPACITY = 21;
	ItemType* items; // Array of heap items
	int itemCount; // Current count of heap items
	int maxItems; // Max capcity of the heap

	// Returns the array index of the left child
	int getLeftChildIndex(const int nodeIndex) const;

	// Returns the array index of the right child
	int getRightChildIndex(int nodeIndex) const;

	// Returns the array index of the parent node
	int getParentIndex(int nodeIndex) const;

	// Tests whether this node is a leaf
	bool isLeaf(int nodeIndex) const;

	// Converts the semiheap to a heap
	void heapRebuild(int nodeIndex);

	// Creates a heap from from unordered array
	void heapCreate();

public:
	ArrayMaxHeap();
	ArrayMaxHeap(const ItemType someArray[], const int arraySize);
	virtual ~ArrayMaxHeap();


	bool isEmpty() const;
	int getNumberOfNodes() const;
	int getHeight() const;
    ItemType peekTop() const;// throw(PrecondViolatedExcep);
	bool add(const ItemType& newData);
	bool remove();
	void clear();
};
// -------------------------------------------------------------------
// getLeftChildIndex: Returns the array index of the left child
// nodeIdex: is the index of the node
// returns the left node index
// -------------------------------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getLeftChildIndex(const int nodeIndex) const
{
	return (2 * nodeIndex) + 1;
}


// ----------------------------------------------------------------------
// getRightChildIndex: Returns the array index of the right child
// nodeIndex: is the index of the right node
// return the right node index
// ----------------------------------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getRightChildIndex(const int nodeIndex) const
{
	return (2 * nodeIndex) + 2;
}


// -------------------------------------------------------------------
// getParentIndex: Returns the parent node index
// nodeIndex: is the index of the parent node
// returns the array index of the parent node
// -------------------------------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getParentIndex(const int nodeIndex) const
{
	return (nodeIndex - 1) / 2;
}

//-------------------------------------------------------------
// isLeaf: Tells us if the node is a leaf
// nodeIdex: is the index of a node
// returns the left child index method
// ------------------------------------------------------------
template<class ItemType>
bool ArrayMaxHeap<ItemType>::isLeaf(const int nodeIndex) const
{
	return (getLeftChildIndex(nodeIndex) >= itemCount);
}

// ------------------------------------------------------------------ -
// heapRebuild: Converts the semi-heap to a heap
// subTreeNodeIndex: the sub-tree array node index
// ------------------------------------------------------------------
template<class ItemType>
void ArrayMaxHeap<ItemType>::heapRebuild(const int subTreeNodeIndex)
{
    // if the node is not a leaf
    if (!isLeaf(subTreeNodeIndex))
    {
        // Get the left and right child index
        int leftChildIndex = getLeftChildIndex(subTreeNodeIndex);
        int largerChildIndex = leftChildIndex;
        int rightChildIndex = getRightChildIndex(subTreeNodeIndex);
        if (rightChildIndex < itemCount)
        {
            // if the right child index is greater than largest child index
            if (items[rightChildIndex].priorityValue > items[largerChildIndex].priorityValue)
                largerChildIndex = rightChildIndex; // set largest child index to right child index
        }

        // if the sub tree node is less than largest child index
        if (items[subTreeNodeIndex].priorityValue < items[largerChildIndex].priorityValue)
        {
            std::swap(items[largerChildIndex], items[subTreeNodeIndex]); // swap the large child index and sub tree node
            heapRebuild(largerChildIndex); // call on the heapRebuild method
        }
    }
}

// -------------------------------------------------
// heapCreate: creates a heap from an unsorted array
// ------------------------------------------------
template<class ItemType>
void ArrayMaxHeap<ItemType>::heapCreate()
{
    // Create a heap from unsorted array
    for (int index = itemCount / 2; index >= 0; index--)
    {
        heapRebuild(index); // call on the rebuild method
    }
}

Last edited on
seeplus (6597)
ArrayMaxHeap.h (2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
// ---------------------------------------------------------------------------
// ArrayMaxHeap: sets the number of items to the max capacity
//-----------------------------------------------------------------------------
template<class ItemType>
ArrayMaxHeap<ItemType>::ArrayMaxHeap() :itemCount(0), maxItems(DEFAULT_CAPACITY)
{
    items = new ItemType[DEFAULT_CAPACITY];
}

// -------------------------------------------------------------------------------------
// ArrayMaxHeap: Allocats memory for the array and copy values
// someArray[]: an array of ItemType
// arraySize: the size of the array ItemType
// -------------------------------------------------------------------------------------
template<class ItemType>
ArrayMaxHeap<ItemType>::ArrayMaxHeap(const ItemType someArray[], const int arraySize) :
    itemCount(arraySize), maxItems(2 * arraySize)
{

    // Allocate the array
    items = new ItemType[2 * arraySize];

    // Copy the given values into the array
    for (int i = 0; i < itemCount; i++)
        items[i] = someArray[i];

    // Reorganize the array into the heap
    heapCreate();
}

// -----------------------------------------
// ~ArrayMaxHeap: delete the items of array
// -----------------------------------------
template<class ItemType>
ArrayMaxHeap<ItemType>::~ArrayMaxHeap()
{
    delete[] items; // delete array of items
}


// ----------------------------------------------
// isEmpty: see if array is empty
// return itemCount when zero
// ----------------------------------------------
template<class ItemType>
bool ArrayMaxHeap<ItemType>::isEmpty() const
{
    return itemCount == 0;
}

// ----------------------------------------------
// getHeight: gets the height of the node
// returns the height of the nodes
// --------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getHeight() const
{
    // Calculate the height
    double y = log(itemCount + 1) / log(2);
    return static_cast<int>(ceil(y));
}


// --------------------------------------------------
// getNumberOfNodes: gets the number of nodes
// returns the number of nodes
// ---------------------------------------------------
template<class ItemType>
int ArrayMaxHeap<ItemType>::getNumberOfNodes() const
{
    return itemCount;
}

// --------------------------------------
// clear: removes all data from the heap
// --------------------------------------
template<class ItemType>
void ArrayMaxHeap<ItemType>::clear()
{
    itemCount = 0;
}


// ---------------------------------------------------------
//peekTop: Gets the data that is in the top of this heap
// returns the the top of the heap
// ----------------------------------------------------------
template<class ItemType>
ItemType ArrayMaxHeap<ItemType>::peekTop() const// throw(PrecondViolatedExcep)
{
    // If the heap is empty throw error
    if (isEmpty())
        throw PrecondViolatedExcep("Attempted peek into an empty heap.");
    return items[0];
}

// ------------------------------------------------------
// add: add values to the heap
// newData: the new data to be added to heap
// returns if adding the new data was successful
// -------------------------------------------------------
template<class ItemType>
bool ArrayMaxHeap<ItemType>::add(const ItemType& newData)
{
    bool isSuccessful = false;

    // if itemCount is less than max items
    if (itemCount < maxItems)
    {
        items[itemCount] = newData;
        bool inPlace = false;
        int newDataIndex = itemCount;

        // While the new data index is greater than zero and not in place
        while ((newDataIndex > 0) && !inPlace)
        {
            int parentIndex = getParentIndex(newDataIndex);

            // If new dtata index is less than parent index
            if (items[newDataIndex].priorityValue < items[parentIndex].priorityValue)
            {
                inPlace = true; // set inPlace to true
            }             else
            {
                std::swap(items[newDataIndex], items[parentIndex]); // swap the index
                newDataIndex = parentIndex; // set new data index to parent index
            }
        }
        itemCount++; // count number of items
        bool isSuccessful = true;
    }
    return isSuccessful;
}

// ------------------------------------
// remove: remove data from the heap
// returns if the removal was successful
// ------------------------------------
template<class ItemType>
bool ArrayMaxHeap<ItemType>::remove()
{
    bool isSuccessful = false;

    // if the heap is not empty
    if (!isEmpty())
    {
        items[ROOT_INDEX] = items[itemCount - 1];
        itemCount--;
        heapRebuild(ROOT_INDEX);
        bool isSuccessful = true;
    }
    return isSuccessful;
}

#endif

seeplus (6597)
driver.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
include "HeapPriorityQueue.h"
#include "PrecondViolatedExcept.h"
#include "Common.h"
#include <iostream>
#include <string>

int main()
{
    HeapPriorityQueue<item> pqPtr;
    item* p = new item[4];

    // Set task and priority values to a number
    p[0].task = "Do coding assignment.";
    p[0].priorityValue = 5;
    p[1].task = "Start the research paper.";
    p[1].priorityValue = 5;
    p[2].task = "Go to the gorcery store.";
    p[2].priorityValue = 3;
    p[3].task = "Watch a movie.";
    p[3].priorityValue = 2;

    // Add task and priority values to queue
    for (int i = 0; i < 4; i++)
    {

        bool success = pqPtr.add(p[i]);
        if (!success)
            std::cout << "Failed to add " << p[i].task << " to the priority queue." << std::endl;
    }

    // Find the task with the largest priority
    for (int i = 0; i < 4; i++)
    {
        try
        {
            std::cout << "The item witht the largest priority: " << pqPtr.peek().task << std::endl;
        }
        catch (PrecondViolatedExcep e)
        {
            std::cout << e.what() << std::endl;
        }

        // Remove funtion with largest priority
        std::cout << "Call remove function" << std::endl;
        pqPtr.remove();
    }
    //system("pause");
    return 0;
}



Rebuild started...
1>------ Rebuild All started: Project: heap, Configuration: Release x64 ------
1>driver.cpp
1>Generating code
1>Previous IPDB not found, fall back to full compilation.
1>All 168 functions were compiled because no usable IPDB/IOBJ from previous compilation was found.
1>Finished generating code
1>heap.vcxproj -> c:\myprogs\heap.exe
========== Rebuild All: 1 succeeded, 0 failed, 0 skipped ==========


Good luck!
Last edited on
Lacy9265 (119)
Got to to run. Thanks for your help @seeplus I really appreciate it.
Topic archived. No new replies allowed.
Pages: 12