插入並堆到堆用數組構建

我想創建一個數組的二進制堆。我已成功地與buildHeap和heapify堆成一堆。我的問題是當我嘗試insert一個新的元素到陣列中，當我嘗試與heapSort分類。插入並堆到堆用數組構建

以下是我對heapify功能：

void heap::Heapify(int arr[], int i){ 
    int largest = i; 
    int L = LeftChild(i); 
    int R = RightChild(i); 
    if (L <= heapSize && arr[L] > arr[i]) 
     largest = L; 
    else{ 
     largest = i; 
    } 

    if (R <= heapSize && arr[R] > arr[largest]){ 
     largest = R; 
    } 
    if(largest != i){ 
     int temp = arr[i]; 
     arr[i] = arr[largest]; 
     arr[largest] = temp; 
     Heapify(arr, largest); 
    } 
}

這裏是我的buildHeap功能：

void heap::BuildHeap(int arr[]){ 
    for(int i = (heapSize/2)-1; i >= 0; i--){ 
     Heapify(arr, i); 
    } 
}

這兩項職能的工作，而下面沒有工作，用於插入它沒有插入到適當的位置。

這裏是insert功能：

void heap::Insert(int arr[], int key){ 
    heapSize++; 
    int i = heapSize - 1; 

    while(i > 0 && arr[Parent(i)] <= key){ 
     arr[i] = arr[Parent(i)]; 
     i = Parent(i); 
    } 

    arr[i] = key; 
}

隨着heapSort函數它被排序它在大多數情況下，但將打印它像這樣（第一行是堆是排序前）：

32 24 5 19 23 4 3 11 2 12 
5 2 4 3 23 19 32 11 24 12

，這裏是我的heapSort功能：

void heap::HeapSort(int arr[]){ 
    for(int i = heapSize - 1; i >= 0; i--){ 
     int temp = arr[0]; 
     arr[0] = arr[i]; 
     arr[i] = temp; 

     heapSize = heapSize - 1; 
     Heapify(arr, 0); 
    } 
}

任何幫助來確定這兩個功能如何不正常工作將不勝感激。

來源

2017-10-10 zsloan112

看起來像一個簡單的調試任務。如果您嘗試交換兩個值，但交換後兩者都相同，而另一個值丟失，那就太糟糕了。對於一個合適的[mcve]，我希望能夠複製粘貼到我的編譯器中，並獲得相同的問題。 –

你真的應該回顧一下二進制堆的理論。序列32 24 5 19 23 4 3 11 2 12看起來不是有效的內容。堆排序不會對堆的內部數據進行排序，而是會逐個提取最小/最大值。 – jszpilewski

'arr [i] = arr [Parent（i）];'也許應該是'std :: swap（arr [i]，arr [Parent（i）]）'' – AndyG

我認爲這個問題是關閉的情況的一個錯誤在這些線路

if (L <= heapSize && arr[L] > arr[i]) 

if (R <= heapSize && arr[R] > arr[largest]){

，他們都應該是<而不是<=，因爲最後一個元素是heapsSize-1。

其他細節

void heap::Heapify(int arr[], int i){ 
    int largest = i; // setting largest to i first time 
    int L = LeftChild(i); 
    int R = RightChild(i); 
    if (L <= heapSize && arr[L] > arr[i]) // compare with arr[i] is not wrong but doesn't express the intent. 
     largest = L; 
    else{ 
     largest = i; // setting largest to i second time 
    } 

    if (R <= heapSize && arr[R] > arr[largest]){ 
     largest = R; 
    } 
    if(largest != i){ 
     int temp = arr[i];  // these 3 lines are the std::swap 
     arr[i] = arr[largest]; // or you could roll your own function that does the same. 
     arr[largest] = temp; // better expressing the intent. 
     Heapify(arr, largest); 
    } 
}

改寫爲

void heap::Heapify(int arr[], int i){ 
    int largest = i; 
    int L = LeftChild(i); 
    int R = RightChild(i); 

    if (L < heapSize && arr[L] > arr[largest]) { 
     largest = L; 
    } 

    if (R < heapSize && arr[R] > arr[largest]) { 
     largest = R; 
    } 

    if(largest != i){ 
     swap(arr[i], arr[largest]); 
     Heapify(arr, largest); 
    } 
}

來源

2017-10-10 21:13:13 Surt

插入並堆到堆用數組構建

回答

相關問題