堆

堆

本章主要介紹堆，下面是關(guān)于堆的一些主要操作：

// 最大堆實(shí)現(xiàn), 數(shù)組下標(biāo)從1開始，a[0]不使用。

// 交換兩數(shù)
void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

// 把第i個元素向上移動
void ShiftUp(int a[], int i) {
    while(i>1 && a[i]>a[i/2]) {
        swap(a[i], a[i/2]);
        i >>= 1;
    }
}

// 把第i個元素向下移動
void ShiftDown(int a[], int n, int i) {
    while((i=2*i) <= n) {
        if(i+1<=n && a[i+1]>a[i]) ++i;
        if(a[i] > a[i/2]) swap(a[i], a[i/2]);
        else break;
    }
}

// 把數(shù)組a變成具備最大堆性質(zhì)的數(shù)組
void MakeHeap(int a[], int n) {
    for(int i=n/2; i>0; --i)
        ShiftDown(a, n, i);
}

// 向堆中插入元素x
void Insert(int a[], int &n, int x) {
    a[++n] = x;
    ShiftUp(a, n);
}

// 刪除堆中第i個元素
void Del(int a[], int &n, int i) {
    a[i] = a[n--];
    if(i>1 && a[i]>a[i/2]) ShiftUp(a, i);
    else ShiftDown(a, n, i);
}

// 堆排序，時間復(fù)雜度O(nlogn)
void HeapSort(int a[], int n) {
    MakeHeap(a, n);
    for(int i=n; i>1; --i) {
        swap(a[i], a[1]);
        ShiftDown(a, i-1, 1);
    }
}