建立一個自下而上的堆

我嘗試從我的課本做堆自下而上從的僞碼構造但是輸出即時得到不正確的堆即時得到了2 9 8 6 5 7建立一個自下而上的堆

有誰知道IM腳麻（僞代碼是一本教科書，並堆需要是數組）

這裏是僞代碼自下而上IM與

//constructs a heap from elements of a given array by bottom up algorithm 
//input an array H[1...n] of orderable items 
//output a heap H[1...n] 

for i<- [n/2] downto 1 do 
k<-i; v<-H[k]; 
heap<-False 
    while not heap and 2*k <= n do 
    j<-2*k 
    if(j<n) //there are two children 
    if H[j] < H[j+1] j<- j+1 
    if v>=h[j] 
    heap = true 
    else H[k]<-H[j] k<-j 
H[k] <-V

在這裏工作是我的代碼

package heapbottomup; 

import javax.swing.Spring; 

public class heapbottomup { 
public static void main(String args[]){ 
    int[] array = {2 ,9 ,7 ,6 ,5 ,8}; 
    BottomUp(array); 
} 

static int[] BottomUp (int[]array){ 
    int n = array.length-1; 

    for(int i=(n/2);i>=1;i--){ 
     int k =i; 
     int v = array[k]; 
     boolean Heap = false; 

     while(!Heap && ((2*k)<=n)){ 
      int j = 2*k; 
      if (j<n){ 
       if(array[j]<array[j+1]) j =j+1; 
      } 
      if(v>=array[j]){ 
       Heap=true; 
      } 
      else{ 
       array[k]= array[j]; 
       k=j; 
      } 
      array[k]=v; 
     }//end while 

    }//end for 
    print(array); 
    return(array); 
} 


static void print(int[]array){ 
    if(array==null){ 
     System.out.println("empty"); 
     return; 
    } 
    for(int i =0;i<array.length;i++){ 
     System.out.print(array[i] + " "); 
    } 
    System.out.println(); 
}//end print 


}

來源

2014-04-08 hockeyfreak863

Java中的數組起始於索引0並轉至n-1（不像僞代碼中的1到n）。你正確地初始化n爲array.length-1，但是你也應該讓for循環去，而i >= 0不是i >= 1。我沒有運行程序來查看是否有其他問題，但這似乎是第一個要解決的問題。

來源

2014-04-08 21:52:03

其更好，但現在我得到的排序堆即時得到9 8 7 6 5 2時，正確的輸出是9 6 8 2 5 7 – hockeyfreak863

從你的僞代碼的縮進，它看起來像過去的行'H [k] <-V'在時間之外，但是在你的代碼中它是在時間之內的。 –

請注意，如果使用1索引數組更容易理解或更快速地進行操作，則可以始終使數組大於必要的數值，並且不要使用第0個條目。 – dfeuer

的關鍵點是：

爲了保持在位置j的一個節點，它的左孩子在2J的財產，其右孩子是在2J +1和其父是與j/2, j的範圍是：1 < = j < = n。
數組範圍是從0到n-1

的訣竅是：在for和while循環，你還以爲範圍1到n，但是當你做數組操作，你只需要偏移1，即位置j的數組[j-1]。

試着用下面的代碼，我測試了它，它的工作 - 輸出是9 6 8 2 5 7.請注意array [k-1] = v不在while循環中。

public class heapbottomup { 
    public static void main(String args[]){ 
     int[] array = {2 ,9 ,7 ,6 ,5 ,8}; 
     BottomUp(array); 
    } 

    static int[] BottomUp (int[]array){ 
     int n = array.length; 

     for(int i=(n/2);i>=1;i--){ 
      int k =i; 
      int v = array[k-1]; 
      boolean Heap = false; 

      while(!Heap && ((2*k)<=n)){ 
       int j = 2*k; 
       if (j<n){ 
        if(array[j-1]<array[j]) j =j+1; 
       } 
       if(v>=array[j-1]){ 
        Heap=true; 
       } 
       else{ 
        array[k-1]= array[j-1]; 
        k=j; 
       }     
      }//end while 

      array[k-1]=v; 

     }//end for 
     print(array); 
     return(array); 
    } 

    static void print(int[]array){ 
     if(array==null){ 
      System.out.println("empty"); 
      return; 
     } 
     for(int i =0;i<array.length;i++){ 
      System.out.print(array[i] + " "); 
     } 
     System.out.println(); 
    }//end print 
}

來源

2014-04-09 05:48:05

建立一個自下而上的堆

回答

相關問題