My function sort sometimes throws an access violation reading a location, and sometimes it works.
I cant find a connection between when it does, and when it doesn't.
The sort function is going to sort the elements in arr with n items by using a d-max-heap. It has to use addToHeap and removeFromHeap.
template <typename Comparable>
void sort(Comparable arr[], int n, int d){
Comparable* tempArray = new Comparable[n];
Comparable* removeArr = new Comparable[n];
makeCopyOfArray(arr, removeArr, n);
buildHeap(removeArr, n, d);
printArray(removeArr, n);
int x = 0;
for (int i = n; i > 0; i--) {
Comparable temp = removeFromHeap(removeArr, i, d);
addToHeap(tempArray, temp, x, d);
x++;
printArray(tempArray, x);
}
for (int y = 0; y < n; y++){
arr[y] = tempArray[y];
}
printArray(arr, n);
}
template <typename Comparable>
void addToHeap(Comparable heap[], Comparable elem, int n, int d){
int parentIndex, tmp, nodeIndex;
if (n == SIZE_OF_ARRAY){
throw "Exception at addToHeap, full array";
}
heap[n] = elem;
n++;
nodeIndex = n - 1;
parentIndex = (n - 1) / d;
while (nodeIndex != 0) {
if (heap[parentIndex] < heap[nodeIndex]) {
tmp = heap[parentIndex];
heap[parentIndex] = heap[nodeIndex];
heap[nodeIndex] = tmp;
}
nodeIndex = parentIndex;
parentIndex = (nodeIndex - 1) / d;
}
}
template <typename T>
void printArray(T arr[], int n){
for (int x = 0; x < n; x++){
cout << arr[x] << " ";
}
cout << endl;
}
template <typename Comparable>
Comparable removeFromHeap(Comparable heap[], int n, int d){
Comparable root = heap[0];
heap[0] = heap[n - 1];
heap[n - 1] = NULL;
rootHeapyfiDown(heap, n - 1, d);
return root;
}
template <typename Comparable>
void rootHeapyfiDown(Comparable heap[], int n, int d){
int x = 1,z=0,y=0, rootIndex=0, indexOfLargestChild=NULL, largestChild=0;
Comparable root = heap[0], temp=NULL;
bool rootLarger = false;
do{
indexOfLargestChild = (rootIndex*d) + 1;
for (y = 1; y < d; y++){
largestChild = heap[indexOfLargestChild];
if (largestChild < heap[(rootIndex*d) + 1+y]){
indexOfLargestChild = (rootIndex*d) + 1+y;
}
}
if (heap[rootIndex] < heap[indexOfLargestChild]){
temp = heap[rootIndex];
heap[rootIndex] = heap[indexOfLargestChild];
heap[indexOfLargestChild] = temp;
rootIndex = indexOfLargestChild;
}
else
rootLarger = true;
} while (rootLarger == false);
}
template <typename Comparable>
int posOfMaxChild(Comparable heap[], int thePos, int n, int d){
int x = 0,child;
child = thePos*d;
while (x < d){ //HITTAR STÖRSTA BARNET
if (child != n && heap[child + x] > heap[child]){
child = child + x;
}
x++;
}
return child;
}
template <typename Comparable>
void buildHeap(Comparable arr[], int n, int d){
for (int i = (n / d) - 1; i>=0; --i){
int child, x = 1;
Comparable tmp = arr[i];
for (; i*d + 1 <= n; i = child){
child=posOfMaxChild(arr, i, n, d);
if (arr[child] > tmp){
arr[i] = arr[child];
arr[child] = tmp;
}
else
break;
}
}
}
It seems to me that you are struggling with d-ary heaps and heapsort. Usually, when dealing with heaps, you will need two auxiliary functions :
sink() : Starting from the top of the heap, you will make permutations to make sure the heap property is satisfied. sink() is necessary to maintain the heap property when you retrieve the top of the heap.swim() : Starting from a given position, you will make permutations going up to enforce the heap condition. swim() is necessary to maintain the heap property when you add elements to the heap.But, if we only want to sort using the heap property, we will only need the sink() because there is no need to add any element anywhere. How does the heapsort work ?
array, we reorder the elements so that the array satisfies the heap property.Here is my heapsort implementation using d-ary heaps as support :
template <typename T>
void sink(T arr[], int pos, int N, int d) {
int start(pos*d + 1), max_index(start);
while(start < N) {
// Find the max amongst direct "children" of position `pos`
for(int i = start + 1; (i < start + d) && (i < N); i++) {
if (arr[i] > arr[max_index]) {
max_index = i;
}
}
// If arr[pos] is less than the max we found, switch them and proceed
if (arr[pos] < arr[max_index]) {
// Switch arr[pos] and arr[max_index] to enforce heap condition
T tmp = arr[pos];
arr[pos] = arr[max_index];
arr[max_index] = tmp;
// Update pos and start to sink "recursively"
pos = max_index;
start = pos*d + 1;
max_index = start;
} else { // Else, there is nothing to worry about further ...
break;
}
}
}
template <typename T>
void dheapsort(T arr[], int N, int d) {
// The for loop "heapify" the array.
for (int k = N/d; k >= 0; k--) {
sink<T>(arr, k, N, d);
}
// We exchange the max (located at arr[0] since the array became a heap)
// with the last element.
// Then we enforce the heap condition on the N-1 remaining elements.
// N is then decreased
// (...) so on.
while (N > 1) {
T tmp = arr[N-1];
arr[N-1] = arr[0];
arr[0] = tmp;
sink<T>(arr, 0, --N, d);
}
}
Then you just have to use it with the parameters you want ... An example :
int main() {
int test[10] = {1, 3, 2, 5, 6, 8, 2, 8, 10, 11};
dheapsort(test, 10, 3);
for (int i = 0; i < 10; i++)
cout << "test[" << i << "] : " << test[i] << endl;
return 0;
}
Outputs :
test[0] : 1
test[1] : 2
test[2] : 2
test[3] : 3
test[4] : 5
test[5] : 6
test[6] : 8
test[7] : 8
test[8] : 10
test[9] : 11
You can see this implementation in action here ...
Now, supposing we have at hands some functions like yours (removeFromHeap, buildHeap ...) :
template <typename T>
void dheapsort(T arr[], int N, int d) {
buildHeap(arr, N, d);
while (N > 1) {
T tmp = removeFromHeap(arr, N, d);
arr[--N] = tmp;
}
}
But your implementations of buildHeap() and removeFromHeap() need to be fixed, I will use my function sink(), thus posOfMaxChild() will no longer be needed. But since posOfMaxChild() was broken, here is a fix ...
template <typename Comparable>
int posOfMaxChild(Comparable heap[], int thePos, int n, int d) {
int child(thePos*d+1), posMax(child);
// You had improper loop conditions ...
for (int x = child + 1; (x < child+d) && (x < n); x++) {
if (arr[posMax] < arr[x])
posMax = x;
}
return (posMax < n) ? posMax : -1;
}
Then goes buildHeap() :
template <typename Comparable>
void buildHeap(Comparable arr[], int n, int d) {
// 1. The first index that might have children is n/d, not (n/d) - 1 !
// Be careful of how integer division works ...
for (int i = (n/d); i>=0; --i){
sink(arr, i, n, d);
}
}
And finally removeFromHeap() :
template <typename Comparable>
Comparable removeFromHeap(Comparable heap[], int n, int d) {
Comparable root = heap[0];
heap[0] = heap[n-1];
sink(heap, 0, n-1, d);
return root;
}
The heapsort implementation using OP's auxiliary functions along with my sink() implementation is fully available HERE. I used the same example array as with my own implementation.