Question

In: Computer Science

C++ Program 2–Implement a Priority queue using a SORTED list. Use Quicksort after adding a new...

C++

Program 2–Implement a Priority queue using a SORTED list. Use Quicksort after adding a new node.Example of quick sort below. Adopt to your program.

#include <iostream>

voidquickSort(inta[], intfirst, intlast);

intpivot(inta[], intfirst, intlast);

voidswap(int& a, int& b);

voidswapNoTemp(int& a, int& b);

voidprint(intarray[], constint& N);

usingnamespacestd;

intmain()

{

inttest[] = { 7, -13, 1, 3, 10, 5, 2, 4 };

intN = sizeof(test)/sizeof(int);

cout << "Size of test array :"<< N << endl;

cout << "Before sorting : "<< endl;

print(test, N);quickSort(test, 0, N-1);

cout << endl << endl << "After sorting : "<< endl;print(test, N);

return0;

}

/**

* Quicksort.

* @param a -The array to be sorted.

* @param first -The start of the sequence to be sorted.

*@param last -The end of the sequence to be sorted.

*/

voidquickSort( inta[], intfirst, intlast )

{

intpivotElement;if(first < last){pivotElement = pivot(a, first, last);

quickSort(a, first, pivotElement-1);

quickSort(a, pivotElement+1, last);

}

}

/**

* Find and return the index of pivot element.

* @param a -The array.

* @param first -The start of the sequence.

* @param last -The end of the sequence.

* @return -the pivot element

*/

intpivot(inta[], intfirst, intlast)

{

intp = first;

intpivotElement = a[first];

for(inti = first+1 ; i <= last ; i++)

{

/* If you want to sort the list in the other order, change "<=" to ">" */if(a[i] <= pivotElement)

{

p++;

swap(a[i], a[p]);

}

}

swap(a[p], a[first]);

returnp;

}

/**

* Swap the parameters.

* @param a -The first parameter.

* @param b -The second parameter.

*/

voidswap(int& a, int& b)

{

inttemp = a;

a = b;

b = temp;

}

/**

* Swap the parameters without a temp variable.

* Warning! Prone to overflow/underflow.

* @param a -The first parameter.

* @param b -The second parameter.

*/

voidswapNoTemp(int& a, int& b)

{

a -= b;

b += a;// b gets the original value of a

a = (b -a);// a gets the original value of b

}

/**

* Print an array.

* @param a -The array.

* @param N -The size of the array.

*/

voidprint(inta[], constint& N)

{

for(inti = 0 ; i < N ; i++)

cout << "array["<< i << "] = "<< a[i] << endl;

}

Solutions

Expert Solution

#include <iostream>
#define MAX_SIZE 10000
#define NULL_VAL (-100000)
int pq_ind = 0;


int top(int pq[]);
void pop(int pq[]);
void push(int pq[],int val);
void  quickSort(int  a[], int  first, int  last);
int  pivot(int  a[], int  first, int  last);
void  swap(int & a, int & b);
void  swapNoTemp(int & a, int & b);
void  print (int  array[], const int & N);
using namespace std;
int  main()
{
    int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
    int N = sizeof(test)/sizeof(int );
    cout << "Size of test array :"<< N << endl;
    cout << "Before sorting : "<< endl;
    print (test, N);
    quickSort(test, 0, N-1);
    cout << endl << endl << "After sorting : "<< endl;
    print (test, N);

    printf("\n\npriority queue Testing \n\n");
    /* priority Queue testing */
    int pq[MAX_SIZE];
    push(pq,45);
    push(pq,10);
    push(pq,78);
    printf("\nafter inserting  45 10 78,the content of priority queue is\n");
    print(pq,pq_ind);
    pop(pq);
    printf("\nafter removing top, the content of priority queue is \n");
    print(pq,pq_ind);
    
    return 0;
}

/* 
 * @param pq -- priority queue int array
 * @param val  --- value to be inserted
 */
void push(int pq[],int val){
    pq[pq_ind++] = val;
    quickSort(pq,0,pq_ind-1);
}



/*
 *@param pq -- priority queue int array
 */
void pop(int pq[]){
    --pq_ind;
}


/*
 *@param pq -- priority queue int array
 */
int top(int pq[]){
    if(pq_ind == 0){
        cout<<"no value present in pq\n";
        return  NULL_VAL;
    } 
    return pq[pq_ind - 1];
}


/**
* Quicksort.
* @param a -The array to be sorted.
* @param first -The start of the sequence to be sorted.
*@param last -The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last )
{
    int pivotElement;
    if(first < last){
        pivotElement = pivot(a, first, last);
        quickSort(a, first, pivotElement-1);
        quickSort(a, pivotElement+1, last);
    }
}
/**
* Find and return  the index of pivot element.
* @param a -The array.
* @param first -The start of the sequence.
* @param last -The end of the sequence.
* @return  -the pivot element
*/
int pivot(int a[], int first, int last)
{
    int p = first;
    int pivotElement = a[first];
    for(int i = first+1 ; i <= last ; i++)
    {
        /* If you want to sort the list in the other order, change "<=" to ">" */
        if(a[i] <= pivotElement)
        {
            p++;
            swap(a[i], a[p]);
        }
    }
    swap(a[p], a[first]);
    return p;
}
/**
* Swap the parameters.
* @param a -The first parameter.
* @param b -The second parameter.
*/
void swap(int & a, int & b)
{
    int temp = a;
    a = b;
    b = temp;
}
/**
* Swap the parameters without a temp variable.
* Warning! Prone to overflow/underflow.
* @param a -The first parameter.
* @param b -The second parameter.
*/
void swapNoTemp(int & a, int & b)
{
    a -= b;
    b += a;// b gets the original value of a
    a = (b -a);// a gets the original value of b
}
/**
* Print  an array.
* @param a -The array.
* @param N -The size of the array.
*/
void print (int a[], const int & N)
{
    for(int i = 0 ; i < N ; i++)
    cout << "array["<< i << "] = "<< a[i] << endl;
}


Related Solutions

C++ Program 1–Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 10...
C++ Program 1–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...
// priorityList.java // a priority queue based on a sorted list // to run this program:...
// priorityList.java // a priority queue based on a sorted list // to run this program: C>java PiorityQApp //////////////////////////////////////////////////////////////// class Link { public long dData; // data item public Link next; // next link in list // ------------------------------------------------------------- public Link(long dd) // constructor { dData = dd; } // ------------------------------------------------------------- public void displayLink() // display this link { System.out.print(dData + " "); } } // end class Link //////////////////////////////////////////////////////////////// class SortedList { private Link first; // ref to first item...
write a java program to Implement a Priority Queue using a linked list. Include a main...
write a java program to Implement a Priority Queue using a linked list. Include a main method demonstrating enqueuing and dequeuing several numbers, printing the list contents for each.
write C program to implement the priority queue with the operation insert
write C program to implement the priority queue with the operation insert
Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements....
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...
Write a C program to implement the priority queue with the operations insert and extractmax. Sample...
Write a C program to implement the priority queue with the operations insert and extractmax. Sample : ====Menu==== insert extractmax display exit Enter your choice: 1 Input a number: 2 enter any key to go to main menu ====Menu==== insert extractmax display exit Enter your choice: 1 Input a number: 4 enter any key to go to main menu ====Menu==== insert extractmax display exit Enter your choice: 1 Input a number: 6 enter any key to go to main menu...
Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is...
Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is the right-most node. The remove (de-queue) operation returns the node with the highest priority (key). If displayForward() displays List (first-->last) : 10 30 40 55 remove() would return the node with key 55. Demonstrate by inserting keys at random, displayForward(), call remove then displayForward() again. You will then attach a modified DoublyLinkedList.java (to contain the new priorityInsert(long key) and priorityRemove() methods). Use the provided...
Language C++ Implement a Priority Queue with a Binary HEAP. Use a Max Heap. Create a...
Language C++ Implement a Priority Queue with a Binary HEAP. Use a Max Heap. 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 Dequeue Dequeue Dequeue...
Implement the minimum priority queue UnsortedMPQ (using vector) that is a child class of the provided...
Implement the minimum priority queue UnsortedMPQ (using vector) that is a child class of the provided MPQ class. The functions from MPQ that are virtual function (remove min(), is empty(), min(), and insert()) must be implemented in the child classes. The functions remove min() and min() should throw an exception if the minimum priority queue is empty. For the UnsortedMPQ class, you will use a vector to implement the minimum priority queue functions. The insert() function should be O(1) and...
In C++, Implement the queue ADT with a singly linked list
In C++, Implement the queue ADT with a singly linked list
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT