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();
}
User contributions licensed under CC BY-SA 3.0