C++

Forum

 
Program with Priority Queue and max Heap structure.

the lone programmer (11)
I am having trouble with a program where I need to write a priority queue and a max heap implementation. We can use a vector to dynamically add elements or use an array. I chose to use a vector since it will be easier. Now what the program does is displays a menu and the user has an option to chose 1.) to add job, 2.) print job, and 3.) view job. The fourth option is to exit the program. the first option is what makes the program and is where I am having trouble because it keeps crashing. If the user presses option one, it will display who is requesting the job, Student, TA, or Instructor. This is where the priority comes in. The instructor has the highest priority, TA coming in second, and student being last. When the user chooses to press option 2 and there are 4 people waiting in the priority, the instructor gets to get printed first and when the user presses option 3 to view jobs there would be three people waiting left. Which could be any of three. Next if there are no instructors waiting to be printed then TA gets to go first then if student is the remaining one then he gets to go. The position will be an integer in the queue starting from one and increments everytime someone gets added. When the user decides to print job or view job its suppose to print out Job #: with the name of who is in the queue. So for exmaple, Job#1: Student, Job#2: TA, Job#3: Instructor, Job#4: Instructor........

THIS IS MY MAX HEAP IMPLEMENTATION
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
 
#pragma once
#include <vector>
struct Heap
{
	std::vector<int> m_elements;

	void ReHeapDown(int root, int bottom);
	void ReHeapUp(int root, int bottom);
	void Swap(int& a, int& b);
};

#include "heap.h"

void Heap::ReHeapDown(int root, int bottom)
{
	int maxChild, rightChild, leftChild;

	leftChild = root * 2 + 1;
	rightChild = root * 2 + 2;

	if (leftChild <= bottom)
	{
		if (leftChild == bottom)
			maxChild = leftChild;
		else
		{
			if (m_elements[leftChild] <= m_elements[rightChild])
				maxChild = leftChild;
			else
				maxChild = leftChild;
		}

		if (m_elements[root] < m_elements[maxChild])
		{
			Swap(m_elements[root], m_elements[maxChild]);
			ReHeapDown(maxChild, bottom);
		}
	}
}

void Heap::ReHeapUp(int root, int bottom)
{
	int parent;
	if (bottom > root)
	{
		parent = (bottom - 1) / 2;
		if (m_elements[parent] < m_elements[bottom])
		{
			Swap(m_elements[parent], m_elements[bottom]);
			ReHeapUp(root, parent);
		}
	}
}

void Heap::Swap(int& a, int& b)
{
	int temp;
	temp = m_elements[a];
	m_elements[a] = m_elements[b];
	m_elements[b] = temp;
}


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
 
priority queue
#include <iostream>
#include "heap.h"
#pragma once

class PQTYPE
{

private:
	Heap m_Items;
	int m_size;

public:
	PQTYPE();
	bool isFull() const;
	bool isEmpty() const;
	void Enqueue(int);
	void Dequeue(int&);
	void printElements();
};

#include "pqtype.h"

PQTYPE::PQTYPE()
{
	m_size = 0;
	m_Items.m_elements.push_back(m_size);
}

bool PQTYPE::isEmpty() const
{
	return m_size == 0;
}

bool PQTYPE::isFull() const
{
	return m_size == 10;
}

void PQTYPE::Enqueue(int newItem)
{
	if (isFull())
		std::cout << "Jobs are full\n";
	else
	{
		m_Items.m_elements.push_back(newItem);
		m_Items.ReHeapUp(0, newItem - 1);
	}
}

void PQTYPE::Dequeue(int& item)
{
	if (isEmpty())
		std::cout << "No jobs to print\n";
	else
	{
		m_Items.m_elements.pop_back();
		m_Items.ReHeapDown(0, item - 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
 
#include"pqtype.h"

int showMenu();
void addJobs(PQTYPE);
void printJobs(PQTYPE);
void viewJobs(PQTYPE);

struct JobPerson
{
	std::string m_Student;
	std::string m_TA;
	std::string m_Instructor;
	static int jobPosition;

	JobPerson();
};

int JobPerson::jobPosition = 1;

JobPerson::JobPerson() : m_Student("Student"), m_TA("TA"), m_Instructor("Instructor")
{
	
}

int main()
{

	int option;
	PQTYPE pq;

	do
	{
		option = showMenu();

		switch (option)
		{
		case 1: addJobs(pq);
		break;
		case 2: printJobs(pq);
		break;
		case 3: viewJobs(pq);
		break;
		case 4:
		break;
		}

	} while (option != 4);


	return 0;
}

int showMenu()
{
	int choice;
	std::cout << " 1.)Add Job\n";
	std::cout << " 2.)Print Job\n";
	std::cout << " 3.)View Jobs\n";
	std::cout << " 4.)Exit\n";
	std::cout << " Enter Choice: ";
	std::cin >> choice;

	return choice;
}

void addJobs(PQTYPE pq)
{
	char jobChoice;

	std::cout << "Who is the job for ( Instructor(i or I), TA(t or T), Student(s or S) :";
	std::cin >> jobChoice;

	if (jobChoice == 'S' || jobChoice == 's' || jobChoice == 'I' || jobChoice == 'i' || jobChoice == 't' || jobChoice == 'T')
	{
		pq.Enqueue();
	}
}

void printJobs(PQTYPE pq)
{
    //to do
}

void viewJobs(PQTYPE pq)
{
	//to do
}
Last edited on
Repeater (3046)
pq.Enqueue();

There's no such function. Enqueue takes an int

Also, presumably you want everything to be operating on the same PQTYPE object? You're passing it by value, so copies are being made. Pass by reference.

m_Items.m_elements.push_back(m_size); This seems odd. You're putting the number zero into the vector. Why?

You never change the value m_size. Is that how you're trying to keep track of how many elements you've added? It never changes.
Last edited on
the lone programmer (11)
I didn't put anything in the Enqueue function because I didn't mean to show you all of it. I have fixed my problem. It now adds items to the vector. here is what I have changed. 

1
2
3
4
5
6
7
8
9
10
11
12
 
void addJobs(PQTYPE& pq, int jp)
{
	char jobChoice;

	std::cout << "Who is the job for ( Instructor(i or I), TA(t or T), Student(s or S) :";
	std::cin >> jobChoice;

	if (jobChoice == 'S' || jobChoice == 's' || jobChoice == 'I' || jobChoice == 'i' || jobChoice == 't' || jobChoice == 'T')
	{
		pq.Enqueue(JobPerson::jobPosition);
	}
}


From my structure I have a static variable and I initialize it to one. The reason I initialized it to one because it needs to start at one and then increment every time I add a new job to the the queue, but it does not increment. When I press the view jobs, it shows the job#1 all the time instead of job#1: then the next line should job#2: job#3: job#4: .......

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
 
#include "pqtype.h"

PQTYPE::PQTYPE()
{
	m_size = 0;
}

bool PQTYPE::isEmpty() const
{
	return (m_size == 0);
}

bool PQTYPE::isFull() const
{
	return (m_size == 10);
}

void PQTYPE::Enqueue(int& newItem)
{
	if (isFull())
		std::cout << "Jobs are full\n";
	else
	{
		m_size++;
		m_Items.m_elements.push_back(newItem);
		m_Items.ReHeapUp(0, m_size - 1);
	}
}

void PQTYPE::Dequeue(int& item)
{
	if (isEmpty())
		std::cout << "No jobs to print\n";
	else
	{
		m_Items.m_elements.pop_back();
		m_size--;
		m_Items.ReHeapDown(0, m_size - 1);
	}
}

void PQTYPE::printElements()
{
	if (isEmpty())
		std::cout << "No jobs to print\n";
	else
	{
		for (int i = 0; i < m_Items.m_elements.size(); i++)
			std::cout << "Job#" << m_Items.m_elements[i] << ":\n";
	}
}


I don't know why it does not increment. I looked at the code and I can't fine the error.
Topic archived. No new replies allowed.