language is C++ Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an ar

ID: 3802091 • Letter: L

Question

language is C++

Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 10 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element,add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill in the blank, etc ( Like prior program done with LISTS )

Create a class called Node: Have a Name and Priority.

Data set - 10 is the highest priority, 1 is lowest priority.

Enqueue and dequeue in the following order.

Function Name, Priority

Enqueue Joe, 3

Enqueue Fred,1

Enqueue Tuyet,9

Enqueue Jose, 6

Dequeue

Enqueue Jing, 2

Enqueue Xi, 5

Enqueue Moe, 3

DequeueEnqueue Miko, 7

Enqueue Vlady, 8

Enqueue Frank, 9

Enqueue Anny, 3

DequeueEnqueue Xi, 2

Enqueue Wali, 2

Enqueue xChe, 6

Enqueue xVerra, 8

Dequeue

Explanation / Answer

Answer:

class PriorityQueueApp
{
    vector<int> input;
    void rightMove(int less, int large);
    void leftMove(int less, int large);
    void constructHeap();
public:
    PriorityQueue(){}
    PriorityQueue(vector<int>& elements)
    {
        input = elements;
        constructHeap();
    }

    void enqueue(int value);

    int dequeue();

    void print();
};
void PriorityQueue::enqueue(int value)
{
    input.push_back(value);
    leftMove(0, input.size() - 1);
    return;
}
int PriorityQueue::dequeue()
{
    assert(input.size() != 0);
    int last = input.size() - 1;
    int read = input[0];
    input[0] = input[last];
    input[last] = read;
    input.pop_back();
    rightMove(0, last-1);
    return read;
}
void PriorityQueue::print()
{
    int size = input.size();
    for (int i = 0; i < size; ++i)
        cout << input[i] << "   ";
    cout << endl;
}
void PriorityQueue::leftMove(int less, int large)
{
    int indexchild = large;
    while (indexchild > less)
    {
        int indexparent = (indexchild-1)/2;

        if (input[indexchild] > input[indexparent])
        {
            int read = input[indexchild];
            input[indexchild] = input[indexparent];
            input[indexparent] = read;

            indexchild = indexparent;
        }
        else
        {
            break;
        }
    }
    return;
}
void PriorityQueue::rightMove(int less, int large)
{
    int number = less;
    while ((number*2)+1 <= large)
    {
        int leftChild = (number * 2) + 1;
        int rightChild = leftChild + 1;
        int exchangeindex = number;

        if (input[exchangeindex] < input[leftChild])
        {
            exchangeindex = leftChild;
        }

        if ((rightChild <= large) && (input[exchangeindex] < input[rightChild]))
        {
            exchangeindex = rightChild;
        }

        if (exchangeindex != number)
        {
            int read = input[number];
            input[number] = input[exchangeindex];
            input[exchangeindex] = read;

            number = exchangeindex;
        }
        else
        {
            break;
        }
    }
    return;
}
void PriorityQueue::constructHeap()
{
    int size = input.size();
    int betweenindex = (size -2)/2;
    while (betweenindex >= 0)
    {
        rightMove(betweenindex, size-1);
        --betweenindex;
    }
    return;
}

Navigate

language is C++ 4) Program Heap Write the code to implement a complete binary he

language is C++ Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an ar

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

language is C++ Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an ar

Question

Explanation / Answer

Related Questions

Navigate