Почему моя функция иногда выдает нарушение прав доступа?

Быстрое слово о кучах и кучи

Мне кажется, что ты борешься с кучей д-ар и кучи.
Обычно при работе с кучами вам понадобятся две вспомогательные функции:

• sink() : Начиная с вершины кучи, вы сделаете перестановки, чтобы убедиться, что свойство кучи удовлетворяется. sink() необходимо поддерживать свойство кучи при извлечении вершины кучи.
• swim() : Начиная с заданной позиции, вы будете делать перестановки, увеличивая условие кучи. swim() необходимо поддерживать свойство кучи при добавлении элементов в кучу.

Но если мы хотим отсортировать только с использованием свойства heap, нам понадобится только sink() потому что нет необходимости добавлять какой-либо элемент в любом месте. Как работает порт?

1. Учитывая начальный array, мы переупорядочиваем элементы так, чтобы массив удовлетворял свойству кучи.
2. После того, как массив является допустимой кучей данных, мы удаляем верхний элемент и сохраняем его в соответствующей позиции в «конце» массива … До тех пор, пока в «куче» ничего не останется.

Моя реализация Heapsort

Вот моя реализация heapsort, использующая кучи d-ary в качестве поддержки:

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);
}
}

Тогда вам просто нужно использовать его с параметрами, которые вы хотите …
Пример :

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;
}

Выходы:

тест [0]: 1
тест [1]: 2
тест [2]: 2
тест [3]: 3
тест [4]: ​​5
тест [5]: 6
тест [6]: 8
тест [7]: 8
тест [8]: 10
тест [9]: 11

Вы можете увидеть эту реализацию в действии Вот …

Реализация с использованием вспомогательных функций ОП:

Теперь предположим, что у нас есть некоторые функции, подобные вашей (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;
}
}

Функция OP исправляет:

Но ваши реализации buildHeap() а также removeFromHeap() нужно исправить, я буду использовать мою функцию sink()таким образом posOfMaxChild() больше не понадобится. Но с тех пор posOfMaxChild() был сломан, вот исправление …

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;
}

Потом идет 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);
}
}

И наконец 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;
}

Пример запускаемого кода

Реализация heapsort с использованием вспомогательных функций OP вместе с моим sink() реализация полностью доступна ВОТ. Я использовал тот же массив примеров, что и в моей собственной реализации.