匿名使用者
匿名使用者 發問時間: 電腦與網際網路程式設計 · 1 0 年前

max heap in java 20點

用JAVA寫出一個可以讀入一串數字(文字檔)並且輸出結果為Max Heap。文字檔讀入,數字之間用一個半形的空白格開,數字串以” [ ”起頭,以” ] ”結束。Ex : 輸入[12 13 4 9 63 52 10 11];輸出依照Binary node編號由小到大依序列出63,13,52,11,12,4,10,9

已更新項目:

更正,不用檔案輸入。執行時用key in的,數字串以” [ ”起頭,以” ] ”結束。

2 個已更新項目:

謝謝ωετμοφντ!

請問如果要以Link-list來表示的話,要怎麼寫呢?

例如:13,63,52 ; 11,13,12 ; 4,52,10 ; 9,11,N ; N,12,N ; N,4,N ; N,10,N ; N,9,N ﹝若連結為Null Node,則以” N “表示﹞

3 個已更新項目:

補充一下,

ex: 13為左子數,63為node值,52為右子數

1 個解答

評分
  • 1 0 年前
    最佳解答

    請參考我的做法

    import java.util.*;

    public class Y00617 {

    private static void createHeap(int[] tmp) {

    int[] heap = new int[tmp.length+1];

    for(int i = 0; i < heap.length; i++)

    heap[i] = -1;

    for(int i = 1; i < heap.length; i++) {

    heap[i] = tmp[i-1];

    int s = i;

    int p = i / 2;

    while(s >= 2 && heap[p] < heap[s]) {

    swap(heap, p, s);

    s = p;

    p = s / 2;

    }

    }

    for(int i = 1; i < heap.length; i++)

    tmp[i-1] = heap[i];

    }

    private static void swap(int[] number, int i, int j) {

    int t;

    t = number[i];

    number[i] = number[j];

    number[j] = t;

    }

    public static void main(String[] args) {

    System.out.print("輸入: ");

    Scanner keyin = new Scanner(System.in).useDelimiter("\\D");

    ArrayList<Integer> al = new ArrayList<Integer>();

    while (keyin.hasNextInt()) {

    al.add(keyin.nextInt());

    }

    int[] ary = new int[al.size()];

    for (int i = 0; i < ary.length; i++) {

    ary[i] = al.get(i);

    }

    createHeap(ary);

    System.out.println(Arrays.toString(ary));

    }

    }

還有問題?馬上發問,尋求解答。