Unknown exception thrown for heap sort

1

I am trying to do heap sort from scratch and I followed the basic logic from here without looking at the pseudocode. I know that heap sort follows from essentially two steps: max heap, and then applying the heap sort logic. I am pretty sure I implemented the algorithm correctly but I get this error when I compile my code:

Unhandled exception at 0x01144CE7 in Heap Sort.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00E02F64).

I saw online that this could be due to an infinite recursion but checking my code it does not seem like that is the case.

Here is my code:

#include <algorithm>
#include <iostream>
#include <vector>
#include <ostream>


template <class T>
void heapify(std::vector<T>& data, int i) {
    int n = data.size();
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    // Case 1: check if left > largest, if it is set largest = left
    if (data[left] > data[largest] && left < n) {
        largest = left;
    }

    // Case 2: check if right > largest, if it is set largest = right
    if (data[right] > data[largest] && right < n) {
        largest = right;
    }

    // Case 3: repeat case 1 and 2 for every exisitng subtree
    if (largest != i) {
        std::swap(data[i], data[largest]); // swap so that the root node will be the largest after each check of the child nodes

        heapify(data, i);
    }
}

template <class T>
void maxHeap(std::vector<T>& data) {
    int n = data.size() - 1;
    for (int i = n / 2; i >= 0; i--) {
        heapify(data, i);
    }
}

template <class T>
void heapSort(std::vector<T>& data) {
    int n = data.size() - 1;
    maxHeap(data);
    for (int i = n; i >= 0; i--) {
        std::swap(data[0], data[i]);
        heapify(data, i); // this is to ensure that we get the largest element as the root
    }
}

template <class T>
void print(std::vector<T>& data) {
    int n = data.size();
    for (int i = 0; i < n; i++) {
        std::cout << data[i] << " " << "\n";
    }
}

int main() {

    std::vector<int> a = { 4,10,3,5,1 };
    heapSort(a);
    print(a);


    std::cin.get();
}
c++
sorting
visual-c++
asked on Stack Overflow Aug 16, 2018 by Snorrlaxxx • edited Aug 16, 2018 by Snorrlaxxx

0 Answers

Nobody has answered this question yet.


User contributions licensed under CC BY-SA 3.0