Priority Queue

#pragma once

template <class TYPE_>
class priorityQueue{

private:
    int capacity;
    int index;
    int numItems;
    TYPE_ * arr;

    void sortTheArr(){

        for(int x = 0 ; x< capacity; x++){
            int smallest = arr[x];
            int index = x ;
            for(int y = x; y < capacity; y++){
                if(arr[y] < smallest){
                    smallest = arr[y];
                    index = y;
                }
                TYPE_ temp = arr[index];
                arr[index] = smallest;

            }
        }
    }

    void resize(int newCap){
        TYPE_ * arr2 = new TYPE_[newCap];

        for(int x  = 0; x < capacity; x++){
            arr2[x] = arr[x];
        }
        delete[] arr;
        arr =  arr2;
        capacity = newCap;
    }

public:

    priorityQueue(){
        capacity = 10;
        index = 0;
        numItems = 0;
        arr = new TYPE_[capacity];
    }

    void insert(TYPE_ item){
        numItems++;
        if(numItems == capacity){
            resize(capacity * 2);
        }
        else{
            //cout<< "inserting "<< item << " into "<< index<<endl;
            arr[index] = item;
            index++;
        }
    }

    TYPE_ extractMin(){
        if(! empty()){
            int smallest = arr[0];
            int ind = 0;
                for(int x = 0; x < index; x++){
                    if(arr[x] < smallest){
                        smallest = arr[x];
                        ind = x;
                    }
                }
                //if(ind != index-1)
                    arr[ind] = arr[index - 1];
                index--;
                numItems --;
            return smallest;
        }
        return -1;
    }

    bool empty(){
        if(numItems <= 0 )
            return true;
        else
            return false;
    }

};






=============================================================================================================================

#pragma once
#include <iostream>
#include "priorityQueue.h"
using namespace std;

template <class THING>
void priorityQueueSort(THING * items, int start, int end)
{
    //declare a variable of type priority queue
    priorityQueue<double> p1;

    //insert the items from the 'items' array into the priority queue, one by one
    for(int x = start; x < end+1; x++){
        p1.insert(items[x]);
        cout << "adding "<< items[x]<< " into "<< x<<endl;
    }

    //extract the items from the priorityQueue one by one and write each value
    // into the 'items' array in the order they come out.
    int count = 0;
    while(!p1.empty()){
        int x = p1.extractMin();
        //cout << "count at: "<< count << "  is: "<< x<<endl;
        items[count] = x;
        count++;
    }
}

int main()
{
    ///////////////////////////////////////////////////
    //Step 1:  Implement an array based priority queue.
    ////////////////////////////////////////////////////

    //A priority queue is an abract data type that supports
    //two operations:  1) insert an item, 'insert(x)', and
    //2) remove and return the smallest item, 'extractMin()'.
    //Implement a priority queue using an array based implementation.
    //Be prepared to answer:
    //What is the run time of your insert method?
    //What is the run time of your extractMin method?
    //What is the run time of your priorityQueueSort function?

    priorityQueue<double> pq;

    pq.insert(57);
    pq.insert(32);
    pq.insert(105);
    pq.insert(17);

    cout << pq.extractMin() << endl; //17
    cout << pq.extractMin() << endl; //32
    cout << endl;

    pq.insert(68);
    pq.insert(5);
    pq.insert(43);

    cout << pq.extractMin() << endl; //5
    cout << pq.extractMin() << endl; //43
    cout << pq.extractMin() << endl; //57
    cout << endl;

    pq.insert(120);
    pq.insert(500);
    pq.insert(3);
    pq.insert(73);
    pq.insert(29);


    //3 29 68 73 105 120 500
    while (!pq.empty())
    {
        cout << pq.extractMin() << endl;
    }
    cout << endl;

    ///////////////////////////////////////////////////////////////////
    //Step 2: now, write a sorting routine that uses a priority queue to sort
    ///////////////////////////////////////////////////////////////////

    //fill a big array with random numbers
    int size = 10;
    int * numbers = new int[size];
    for (int i = 0; i < size; i++)
    {
        //numbers[i] = rand();
        numbers[i] = i *i;
        cout << "original " << numbers[i] << endl;
    }

    //sort the array using a priority queue to help you
    priorityQueueSort(numbers, 0, size - 1);

    //now array should be in sorted order
    for (int i = 0; i < size; i++)
    {
        cout << "sorted ";
        cout << numbers[i] << endl;
    }


    return 0;
}