通過數組實現遇到Downheap算法問題

我目前正在嘗試使用Down-heap算法對我的數組進行排序。但是，當我顯示新排序的數組時，會出現新的數字，並且順序看起來不正確。我不知道我的算法是否有問題，或者我沒有使用這種排序算法的適當條件。通過數組實現遇到Downheap算法問題

我的工作是對20個鍵的數組進行排序。

的代碼：

/* Downheap sorting algorithm */ 
for(i=0; i<20; i++) 
{ 
    j = i + 1; 

    /* If parent is less than both children */ 
    if(key[j] < key[2*j] && key[j] < key[(2*j)+1]) 
    { 
     /* Check which child is smallest */ 
     if(key[2*j] < key[(2*j)+1]) 
     { 
      /* Parent is assigned smallest node */ 
      swap(&key[j],&key[2*j]); 
     } 
     else{swap(&key[j],&key[(2*j)+1]);} 
    } 

    /* If parent is less than left child */ 
    else if(key[j] < key[2*j]) 
    { 
     swap(&key[j],&key[2*j]); 
    } 

    /* If parent is less than right child */ 
    else if(key[j] < key[(2*j)+1]) 
    { 
     swap(&key[j],&key[(2*j)+1]); 
    } 
}

交換函數：

void swap(int *parent, int *child) 
{ 
    int temp; 
    temp = *child; 
    *child = *parent; 
    *parent = temp; 
}

鍵的陣列之前排序：

54,90,137,260,185,65,208,139,114,176,186,77,137,139,178,57,203,110,80,127

陣列鍵排序後的一次：

54,137,185,260,114,77,208,178,110,176,186,65,137,139,139,64,203,90,84,127

64是不存在之前。 57在哪裏？ 80消失了，84從哪裏來？

任何幫助將不勝感激！

來源

2014-11-03 Plaidypus

您可能想要檢查循環的終止條件：定義了多少個數組元素，ond（2 * j）+ 1'get有多大？ – greybeard 2014-11-03 08:04:16

事實證明，我的文件（我沒有提及我從一個文件中讀取這些數字，顯示爲20x10矩陣）在每行的末尾有額外的空格。我解決了這個問題，算法運行得很好。 – Plaidypus 2014-11-04 05:13:04

對於一個測試，使數組大兩倍+ 1，並在讀入之前用鍵的最小值和最大值進行初始化（即使看到您接受了解決同一問題的答案）。 – greybeard 2014-11-04 05:29:17

如果您有一個由20個數組組成的數組，它們通常是key [0] ... key [19]，並且需要考慮堆中一個或多個子元素不存在的可能性，因爲他們的數組位置會離開陣列的邊緣。隨着堆數0..19，那麼元素i的孩子將在2i + 1和2i + 2，所以0有孩子1和2,1有孩子3和4 ... 8有孩子17和18，但9 19歲時只有一個孩子，10個孩子根本沒有孩子。

您是否期待Downheap執行所有排序工作？通常，如http://en.wikipedia.org/wiki/Heapsort所述，Downheap是Heapsort的一部分，但不是全部。

來源

2014-11-03 05:53:06 mcdowella

Woops。好像我錯過了那堂課！我會檢查鏈接並嘗試將它們放在一起。謝謝！ – Plaidypus 2014-11-03 06:09:21

通過「DownHeap」我asuming你的意思是最小堆

算法中的最小堆：

public void insert(Comparable x) { if(size == heap.length - 1) doubleSize();

//Insert a new item to the end of the array 
int pos = ++size; 

//Percolate up 
for(; pos > 1 && x.compareTo(heap[pos/2]) < 0; pos = pos/2) 
    heap[pos] = heap[pos/2]; 

heap[pos] = x;

}」

檢查此鏈接瞭解最小堆min heap

來源

2014-11-03 05:50:16

通過數組實現遇到Downheap算法問題

回答

相關問題