c++ - 为什么我的函数有时会引发访问冲突？

Question

我的函数 sort 有时会在读取位置时抛出访问冲突，但有时却能正常工作。

我找不到它何时发生和何时不发生之间的联系。

排序函数将使用 d-max-heap 对 arr 中具有 n 项的元素进行排序。它必须使用 addToHeap 和 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;
        }
    }
}

Answer 1

简单介绍堆和堆排序

在我看来，您正在为 d 元堆和堆排序而苦苦挣扎。通常，在处理堆时，你会需要两个辅助函数:

• sink() :从堆的顶部开始，您将进行排列以确保满足堆属性。 sink() 是获取堆顶部时维护堆属性所必需的。
• swim() :从给定位置开始，您将进行向上排列以强制执行堆条件。 swim() 是在向堆中添加元素时维护堆属性所必需的。

但是，如果我们只想使用堆属性进行排序，我们只需要 sink() 因为不需要在任何地方添加任何元素。堆排序如何工作？

1. 给定一个初始数组，我们重新排列元素，使数组满足堆属性。
2. 在数组成为有效的 d 元堆后，我们移除顶部元素并将其存储在数组“末尾”的适当位置......直到“堆”中没有任何剩余。<

我的 Heapsort 实现

这是我使用 d 元堆作为支持的堆排序实现:

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

输出:

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

您可以在实际操作中看到此实现 here ...

使用OP的辅助函数实现:

现在，假设我们手头有一些像您的函数(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;
}

可运行代码示例

使用 OP 辅助函数的堆排序实现以及我的 sink() 实现完全可用 HERE .我使用了与我自己的实现相同的示例数组。