How do you write a C plus plus program for the two dimensional array representation of a priority queue?

Answer 1

There are three ways to sort a two-dimensional array. We can sort each row so that the rows remain where they are but the elements within each row are sorted. Or we can sort the rows themselves so the elements within each row remain where they are but the rows are sorted. Or we can do both, sorting the elements in each row and then sorting the rows. The following program demonstrates all three methods using the same bubble-sort method (see the sort function near the top of the code).

Keep in mind that a two-dimensional array is nothing more than a one-dimensional array of one-dimensional arrays. That is, array A[2][3] is a one-dimensional array of 2 elements where each element is a one-dimensional array of 3 elements. In other words, 2 rows with 3 elements per row. However, while static two-dimensional arrays must have the same number of elements in each row, dynamic two-dimensional arrays can have variable length rows. This is achieved by maintaining a one-dimensional array of pointers on the stack or on the heap, where each pointer refers to a separate row. The elements within each row must be contiguous, but the rows themselves can reside anywhere in memory, non-contiguously, and each row can have a different length. If the rows are the same length then you can access the individual elements just as you would with a static array using array subscripts. However, with variable length rows, you must dereference the row and determine its length before accessing the elements within that row.

The program below uses vectors rather than arrays, but a vector is really nothing more than a one-dimensional dynamic array that knows its own size at all times. Vectors are therefore much easier to work with than arrays because all the memory allocations are done for us Behind the Scenes. A two-dimensional vector is nothing more than a vector of vectors which is easier to imagine as begin a vector of rows, where each row has variable length. However, the example below uses fixed-length vectors to implement an array of 5 rows with 4 elements per row.

Due to the fact that every row must be contiguous within itself and that rows may have variable length, it is always going to be easier to sort two-dimensional arrays by row rather than by column. If you need to sort by column rather than row, rather than write a separate and needlessly complex function to cater for this, it is simpler to just orient your array in memory or on disk so that you can sort by row instead. Note that it is trivial to change the orientation of an array whilst printing the array (simply swap the inner and outer loops) so there is no need to physically store the data in the same orientation as the output. The only thing that actually changes is how you visualise the data: whether as a vector of horizontal rows (actual rows) or as a vector of vertical rows (actual columns).

#include<iostream>

#include<iomanip>

#include<vector>

#include<random>

#include<time.h>

template<typename T>

void sort (std::vector<T>& A)

{

unsigned unsorted = A.size();

if (unsorted > 1)

{

do

{

unsigned new_size = 0;

for (unsigned index=1; index<unsorted; ++index)

{

if (A[index]<A[index-1])

{

std::swap (A[index], A[index-1]);

new_size = index;

}

}

unsorted = new_size;

} while (unsorted);

}

}

template<typename T>

void print_array(std::vector< std::vector<T> >& arr)

{

for (unsigned row=0; row<arr.size(); ++row)

{

for (unsigned col=0; col<arr[row].size(); ++col)

{

std::cout << '\t' << arr[row][col];

}

std::cout << std::endl;

}

std::cout << std::endl;

}

template<typename T>

void randomise_array(std::vector< std::vector<T> >& arr)

{

// Pseudo-random number generator (range: 1 to 50).

std::default_random_engine generator;

generator.seed ((unsigned) time (NULL));

std::uniform_int_distribution<unsigned> distribution (1, 50);

for (unsigned row=0; row<arr.size(); ++row)

{

for (unsigned col=0; col<arr[row].size(); ++col)

{

arr[row][col] = distribution (generator);

}

}

}

int main()

{

// Instantiate a 5x4 array

std::vector< std::vector<unsigned> > original (5);

for (unsigned row=0; row<5; ++row)

original[row].resize (4);

randomise_array(original);

// Always work from a copy of the original

std::vector< std::vector<unsigned> > copy = original;

std::cout << "Original array:\n" << std::endl;

print_array(copy);

std::cout << "Sort each row individually:\n" << std::endl;

for (unsigned row=0; row<copy.size(); ++row)

sort (copy[row]);

print_array(copy);

copy = original;

std::cout << "Original array:\n" << std::endl;

print_array(copy);

std::cout << "Sort the rows:\n" << std::endl;

sort(copy);

print_array(copy);

copy = original;

std::cout << "Original array:\n" << std::endl;

print_array(copy);

std::cout << "Sort each row individually and then sort the rows:\n" << std::endl;

for (unsigned row=0; row<copy.size(); ++row)

sort (copy[row]);

sort (copy);

print_array(copy);

}

Example output:

Original array:

43 14 8 5

15 12 49 9

31 27 4 35

15 11 37 6

32 42 35 4

Sort each row individually:

5 8 14 43

9 12 15 49

4 27 31 35

6 11 15 37

4 32 35 42

Original array:

43 14 8 5

15 12 49 9

31 27 4 35

15 11 37 6

32 42 35 4

Sort the rows:

15 11 37 6

15 12 49 9

31 27 4 35

32 42 35 4

43 14 8 5

Original array:

43 14 8 5

15 12 49 9

31 27 4 35

15 11 37 6

32 42 35 4

Sort each row individually and then sort the rows:

4 27 31 35

4 32 35 42

5 8 14 43

6 11 15 37

9 12 15 49

Answer 2

To sort a two-dimensional array, you can either sort the rows, the columns or both. To sort both you need to sort the rows and then the columns, or the columns and then the rows, depending on whatever it is you want to achieve by sorting them.

By way of an example, consider an array of fixed-length strings. Each string is itself an array, thus you could either sort the individual strings first (thus "cat" becomes "act"), and then sort the string array based on the new strings, or you can sort the array based on the existing strings before sorting the strings themselves. Or you can just sort the string array alone.

Either way you simply treat the dimensions as separate one-dimensional arrays and sort them as you would any one-dimensional array.

Not to be pedantic, but bubble sorting is not considered a worthwhile algorithm these days (many consider it an example of how not to write algorithms). For small lists, an insertion sort is preferred as it closely mimics the way a human sorts things.

Answer 3

It took a while to figure out why you would want two-dimensions to represent a priority queue but then it occurred to me that the first dimension could be used to represent the priority, while the second could be used to represent the objects of that priority. In other words, we represent the priority queue as an array of queues, one for each priority, where high-priority queues always take precedence over lower priority queues. New objects simply join the end of the appropriate queue.

A two-dimensional array is really just a one-dimensional array of one-dimensional arrays. In this case we need to use a dynamic array of dynamic arrays. The first dimension can be fixed size if we know how many priorities we need to accommodate, but in generic programming we might need a different number of priorities depending on the type of object we want to place in the priority queue. Therefore we'll use the dynamic option, and allow new priorities to be added as they become necessary.

The only real problem is that objects cannot decide their own priority. In a traditional priority queue, new objects are pushed onto the end of the queue, then the queue is sorted by a comparator (defaulting to the inverse of the object's less-than comparison operator). Thus objects find their correct place in the queue automatically.

By creating separate arrays for each priority, we no longer need a comparator, but there's no obvious way to decide an object's priority. When we add the first object, normally it would just go the front of the queue no matter what its priority. If an object with greater priority is added, it would automatically "push" its way to the front. But with a two-dimensional array, this is no longer possible.

One solution would be to place dummy objects in each queue and thus provide new objects with something to compare with, but there's no practical method of achieving that since the queue cannot construct objects of a given priority; it has no way of determining how to construct objects of a given type other than through the object's default, copy or move constructors -- it cannot cater for user-defined constructors that would define unique priorities.

One way to deal with this problem is to ensure all objects in the queue are derived from the same base object, one that physically holds the derived object's priority, but this then means every object then stores its own priority whilst in the queue. The priority is only useful for determining which queue to add the object to, so it makes no sense to store it inside the object once it is added. We might as well just pass the priority as an argument to the queue's push method instead.

The following program shows one method of implementing a priority queue using a vector of vectors (a dynamic array of dynamic arrays). The program simulates an accident and emergency ward where 5 patients arrive one after the other with random injury levels (where level 1 has the highest priority and level 10 the lowest). The priority queue determines the order the patients are processed. Note that if you attempt to access the top value in an empty queue, an exception will be thrown (the exception is necessary to prevent undefined behaviour). So long as you test that the queue is not empty before calling priority_queue::top(), there is no need for a try-catch block.

#include<iostream>

#include<vector>

#include<random>

#include<ctime>

class patient

{

char m_id;

unsigned m_injury;

public:

patient (const char id, const unsigned injury): m_id(id), m_injury(injury) {}

patient (const patient& other): m_id(other.m_id), m_injury(other.m_injury) {}

char id() const { return m_id; }

unsigned injury() const { return m_injury; }

};

std::ostream& operator<< (std::ostream& os, const patient& p)

{

return os << "patient: " << p.id() << " injury level: " << p.injury();

}

bool operator< (const patient& a, const patient& b)

{

return a.injury() < b.injury();

}

template<typename T>

class priority_queue

{

using container = std::vector<std::vector<T>>;

container m_data;

public:

void push (const T& value, const unsigned priority=0);

void pop ();

const T& top() const;

bool empty() const;

};

template<typename T>

void priority_queue<T>::push (const T& value, const unsigned priority)

{

if (priority+1>m_data.size())

m_data.resize (priority+1);

m_data[priority].push_back (value);

}

template<typename T>

void priority_queue<T>::pop (void)

{

for (std::vector<std::vector<T>>::iterator it=m_data.begin(); it!=m_data.end(); ++it)

{

if (!(*it).empty())

{

std::vector<T>::iterator curr=(*it).begin();

std::vector<T>::iterator next=curr;

while (++next != (*it).end())

{

(*curr) = (*next);

curr = next;

}

(*it).pop_back();

return;

}

}

}

template<typename T>

const T& priority_queue<T>::top() const

{

std::vector<std::vector<T>>::const_iterator it=m_data.begin();

while (it!=m_data.end() && (*it).empty())

++it;

if (it==m_data.end())

throw std::range_error ("priority_queue<T>::top() - the queue is empty!");

return (*it).front();

}

template<typename T>

bool priority_queue<T>::empty() const

{

std::vector<std::vector<T>>::const_iterator it=m_data.begin();

while (it !=m_data.end() && (*it).empty())

++it;

return it==m_data.end();

}

int main()

{

std::default_random_engine generator ((unsigned) time (0));

std::uniform_int_distribution<unsigned> distribution (1, 10);

priority_queue<patient> patients;

std::cout << "Patients arrived in this order:\n";

for (unsigned i=0; i<5; ++i)

{

patient p('A'+i, distribution (generator));

std::cout << p << std::endl;

patients.push (p, p.injury());

}

std::cout << "Patients treated in this order:\n";

while (!patients.empty())

{

std::cout << patients.top() << std::endl;

patients.pop();

}

}

Answer 4

It took a while to figure out why you would want two-dimensions to represent a priority queue but then it occurred to me that the first dimension could be used to represent the priority, while the second could be used to represent the objects of that priority. In other words, we represent the priority queue as an array of queues, one for each priority, where high-priority queues always take precedence over lower priority queues. New objects simply join the end of the appropriate queue.

A two-dimensional array is really just a one-dimensional array of one-dimensional arrays. In this case we need to use a dynamic array of dynamic arrays. The first dimension can be fixed size if we know how many priorities we need to accommodate, but in generic programming we might need a different number of priorities depending on the type of object we want to place in the priority queue. Therefore we'll use the dynamic option, and allow new priorities to be added as they become necessary.

The only real problem is that objects cannot decide their own priority. In a traditional priority queue, new objects are pushed onto the end of the queue, then the queue is sorted by a comparator (defaulting to the inverse of the object's less-than comparison operator). Thus objects find their correct place in the queue automatically.

By creating separate arrays for each priority, we no longer need a comparator, but there's no obvious way to decide an object's priority. When we add the first object, normally it would just go the front of the queue no matter what its priority. If an object with greater priority is added, it would automatically "push" its way to the front. But with a two-dimensional array, this is no longer possible.

One solution would be to place dummy objects in each queue and thus provide new objects with something to compare with, but there's no practical method of achieving that since the queue cannot construct objects of a given priority; it has no way of determining how to construct objects of a given type other than through the object's default, copy or move constructors -- it cannot cater for user-defined constructors that would define unique priorities.

One way to deal with this problem is to ensure all objects in the queue are derived from the same base object, one that physically holds the derived object's priority, but this then means every object then stores its own priority whilst in the queue. The priority is only useful for determining which queue to add the object to, so it makes no sense to store it inside the object once it is added. We might as well just pass the priority as an argument to the queue's push method instead.

The following program shows one method of implementing a priority queue using a vector of vectors (a dynamic array of dynamic arrays). The program simulates an accident and emergency ward where 5 patients arrive one after the other with random injury levels (where level 1 has the highest priority and level 10 the lowest). The priority queue determines the order the patients are processed. Note that if you attempt to access the top value in an empty queue, an exception will be thrown (the exception is necessary to prevent undefined behaviour). So long as you test that the queue is not empty before calling priority_queue::top(), there is no need for a try-catch block.

#include

#include

#include

#include

class patient

{

char m_id;

unsigned m_injury;

public:

patient (const char id, const unsigned injury): m_id(id), m_injury(injury) {}

patient (const patient& other): m_id(other.m_id), m_injury(other.m_injury) {}

char id() const { return m_id; }

unsigned injury() const { return m_injury; }

};

std::ostream& operator<< (std::ostream& os, const patient& p)

{

return os << "patient: " << p.id() << " injury level: " << p.injury();

}

bool operator< (const patient& a, const patient& b)

{

return a.injury() < b.injury();

}

template

class priority_queue

{

using container = std::vector>;

container m_data;

public:

void push (const T& value, const unsigned priority=0);

void pop ();

const T& top() const;

bool empty() const;

};

template

void priority_queue::push (const T& value, const unsigned priority)

{

if (priority+1>m_data.size())

m_data.resize (priority+1);

m_data[priority].push_back (value);

}

template

void priority_queue::pop (void)

{

for (std::vector>::iterator it=m_data.begin(); it!=m_data.end(); ++it)

{

if (!(*it).empty())

{

std::vector::iterator curr=(*it).begin();

std::vector::iterator next=curr;

while (++next != (*it).end())

{

(*curr) = (*next);

curr = next;

}

(*it).pop_back();

return;

}

}

}

template

const T& priority_queue::top() const

{

std::vector>::const_iterator it=m_data.begin();

while (it!=m_data.end() && (*it).empty())

++it;

if (it==m_data.end())

throw std::range_error ("priority_queue::top() - the queue is empty!");

return (*it).front();

}

template

bool priority_queue::empty() const

{

std::vector>::const_iterator it=m_data.begin();

while (it !=m_data.end() && (*it).empty())

++it;

return it==m_data.end();

}

int main()

{

std::default_random_engine generator ((unsigned) time (0));

std::uniform_int_distribution distribution (1, 10);

priority_queue patients;

std::cout << "Patients arrived in this order:\n";

for (unsigned i=0; i<5; ++i)

{

patient p('A'+i, distribution (generator));

std::cout << p << std::endl;

patients.push (p, p.injury());

}

std::cout << "Patients treated in this order:\n";

while (!patients.empty())

{

std::cout << patients.top() << std::endl;

patients.pop();

}

}