Anonymous
Anonymous asked in 電腦與網際網路程式設計 · 1 decade ago

這一題C++不太董想請大大幫忙解決

將下列的資料20,30,10,50,60,40,45,5建立成一棵

Min-Heap。

1 Answer

Rating
  • ?
    Lv 5
    1 decade ago
    Favorite Answer

    #include <iostream>

    #include <iomanip>

    using namespace std;

    const int Max = 32; //最大數量

    int heap[Max+1]; // Min-Heap 陣列

    int Hsize=0; // Heap內數量

    // 調整 ---

    int Hup(int i)

    {

    int y = heap[i];

    for (int c=i/2; c>0 && y < heap[c]; c/=2)

    {

    heap[i] = heap[c];

    i = c;

    }

    heap[i] = y;

    return i;

    }

    // 插入 ---

    int Heap_insert(int data)

    {

    if (Hsize == Max) return 0;

    heap[++Hsize]=data;

    return Hup(Hsize);

    }

    // 以樹狀顯示 ---

    void ShowHeap()

    {

    int p=1;

    while(p<=Hsize) p*=2;

    cout << "\nMinHeap:\n" << setw(--p);

    for(int i=1, n=1; i<=Hsize; i++, n=p*2-1)

    {

    cout << " " << heap[i] << setw(n);

    if (!(i&(i+1))) cout << endl << setw(p=(p-1)/2);

    }

    cout << endl;

    }

    // 主程式 ===

    int main()

    {

    int d[] = { 20, 30, 10, 50, 60, 40, 45, 5 };

    int num = sizeof(d)/sizeof(int);

    for(int i=0; i<num; i++)

    Heap_insert( d[i] );

    ShowHeap();

    system("pause");

    return 0;

    }

    執行結果 :

    MinHeap:

    5

    10 20

    30 60 40 45

    50

    請按任意鍵繼續 . . .

    輸出可以不用像上面那樣玩, 可以直接整串顯示 :

    5 10 20 30 60 40 45 50

    只是較不直覺化而已... ^_^

Still have questions? Get your answers by asking now.