#include<iostream>

#include<ctime>

usingnamespace std;

// 注意父子的計算方式,。節(jié)點編號從0開始,。

inlineint parent(constint x) { return ((x-1)/2); }

inlineint left(constint x) { return (2*x+1); }

inlineint right(constint x) { return (2*x+2); }

int cmp = 0;    // 總共執(zhí)行比較操作的次數(shù)

int swp = 0;    // 總共執(zhí)行交換操作的次數(shù)

// 調(diào)整以i為根的子樹，使之成為最大堆,，size為堆的大小

void maxHeapify(int a[], int size, int i)

{

    cmp +=2;

    swp++;

    int l = left(i);

    int r = right(i);

    int largest = i;    // 最大堆的根

    if( (l < size) && (a[l] > a[i]) )        largest = l;

    if( (r < size) && (a[r] > a[largest]) )  largest = r;

    if( largest != i )

    {

        swap(a[i], a[largest]);         // 三個節(jié)點中較大者成為根

        maxHeapify(a, size, largest);   // 可能破壞了堆性質(zhì),，重新調(diào)整

    }

}

void buildMaxHeap(int a[], int size)    // 建堆

{

    for(int i = (size-1)/2; i>=0; i--)

    {

        maxHeapify(a, size, i);

    }

}

void heapSort(int a[], int size)        // 堆排序,，(n-1)*O(lgn) = O(nlgn)

{

    swp++;

    buildMaxHeap(a, size);

    for(int i=size-1; i>0; i--)         // 重復(fù)n-1次

    {

        swap(a[0], a[i]);

        size--;

        maxHeapify(a, size, 0);         // 每次調(diào)整，花費為O(lgn)

    }

}

int main()

{

    int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

    heapSort(a, sizeof(a)/sizeof(a[0]));

    cout << "總共進行比較 " << cmp << " 次,，總共進行交換 " << swp << " 次" << endl;

    for(int i=0; i<sizeof(a)/sizeof(a[0]); i++)

    {

        cout << a[i] << " ";

    }

    cout << endl;

    return 0;

}

7.

整型數(shù)據(jù)求平均數(shù)方法    考慮到溢出的情況

1. int averagePerfect(int a, int b)  
2. {  
3.     return (a&b) + ((a^b) >>　1);  
4. }