Question

I need a C++ algorithm that implements heapsort using std::priority_queue:

template<typename T>

void heapsort(std::vector<T>& Vec) {

//code here

}

(Vec is populated in tester file)

Answer 1

CODE

void Swap(std::vector<int>& vHeap, std::vector<int>::size_type i, std::vector<int>::size_type j)
{
    if(i == j)
        return;

    int temp;
    temp = vHeap[i];
    vHeap[i] = vHeap[j];
    vHeap[j] = temp;
}

void Sift(std::vector<int>& vHeap, const std::vector<int>::size_type heapSize, const std::vector<int>::size_type siftNode)
{
    std::vector<int>::size_type i, j;

    j = siftNode;
    do
    {
        i = j;
        if(((2*i + 1) < heapSize) && vHeap[j] < vHeap[2*i + 1])
            j = 2*i + 1;
        if(((2*i + 2) < heapSize) && vHeap[j] < vHeap[2*i + 2])
            j = 2*i + 2;

        Swap(vHeap, i, j);
    }
    while(i != j);
}

void MakeInitialHeap(std::vector<int>& vHeap)
{
    for(int i = vHeap.size() - 1; i >= 0; --i)
    {
        Sift(vHeap, vHeap.size(), i);
    }
}

void heapsort(std::vector<int>& vHeap)
{
    MakeInitialHeap(vHeap);
    for(std::vector<int>::size_type i = vHeap.size()-1; i > 0; --i)
    {
        Swap(vHeap, i, 0);
        Sift(vHeap, i, 0);
    }
}