[C++]数据结构之堆-上滤下滤以及用于排序

#include<iostream>
using namespace std;

/*
* 堆，就是一棵完全二叉树，物理存储方式是数组，一般情况下，都牺牲第一个元素arr[0]，剩下的就满足了从1开始计数
* 若堆从1开始计数，那么对于一个节点i，2*i是它的左孩子，2*i+1是它的右孩子
* 对的最基本操作，包括上滤和下滤
* 上滤是指：h(1,n-1)是堆，h(1,n)不是堆，因此通过将arr[n]元素上滤，来达到调整堆的目的
* 下滤是指：h(2,n)是堆，h(1,n)不是堆，因此通过将arr[1]元素下滤，来达到调整堆的目的
*/

#define HEAP_SIZE 10 //这里，我要要建一个堆，堆里面要放10个元素
#define ARR_SIZE (HEAP_SIZE+1) //之前说过，堆默认的实现是牺牲掉第0个元素
#define HeapElemType int //定义堆的元素类型

//HeapElemType  HeapArray[ARR_SIZE];//堆的存储空间

/*
* 大顶堆，上面的，是最大的
* 堆的基本操作：上滤
* h(1,n-1)是堆，h(1,n)非堆，也就是说，只要调整第n个元素，就是一个新堆了
* 注意：n是当前可用元素的最大下标，它是不能超过ARR_SIZE的
*/
void shiftUp(HeapElemType  HeapArray[], int n){
    HeapElemType tmp = HeapArray[n];
    while(n/2>=1 && tmp>HeapArray[n/2]){
        HeapArray[n] = HeapArray[n/2];
        n = n/2;
    }
    HeapArray[n] = tmp;
}

/*
* 大顶堆，上面的，是最大的
* 堆的基本操作：下滤
* h(2,n)是堆，h(1,n)不是堆，也就是所，只要调整第1个元素，就是一个新的大顶堆
* 注意：n是当前堆中元素的最大下表，是不能超过ARR_SIZE的
*/
void shiftDown(HeapElemType  HeapArray[], int first, int n){
    HeapElemType tmp = HeapArray[first];
    int father=first,child;
    while( (child=2*father) <= n){
        //获取孩子中较大的孩子下标
        if(child+1<=n && HeapArray[child]<HeapArray[child+1]) child++;
        //比较源节点和较大孩子，看是否需要继续调整
        if(tmp>HeapArray[child]) break;
        //否则的话，孩子往上走
        HeapArray[father] = HeapArray[child];
        father = child;
    }
    HeapArray[father] = tmp;
}
void printHeapArr(const HeapElemType  HeapArray[], const int n){
    for(int i=1; i<=n; ++i){
        cout<<HeapArray[i]<<" ";
    }
    cout<<endl;
}
void swap(HeapElemType  HeapArray[],int i,int j){
    HeapElemType tmp =     HeapArray[i];
    HeapArray[i] = HeapArray[j];
    HeapArray[j] = tmp;
}
/*
* 堆排序：用堆的属性，即大顶堆最顶部的就是最大的节点
* 因此我们可以每次将根节点和末尾节点交换，然后将除了末尾节点的其他节点重新调整一个堆，然后循环
* 在做上一步之前，需要将杂乱的节点调整成一个堆
*/
void heapsort(HeapElemType  HeapArray[],int n){
    //第一步，先将杂乱的数组调整成一个大顶堆，需要n/2次调整就可以
    int tmp=0;
    for(tmp=n/2; tmp>=1; tmp--){
        shiftDown(HeapArray,tmp,n);
    }
    //第二步，交换第一个节点（最大值）和末尾节点，然后调整除了末尾节点的其他节点为一个新大顶堆
    for(tmp=n;tmp>1;tmp--){
        swap(HeapArray,1,tmp);
        shiftDown(HeapArray,1,tmp-1);
    }
}
void main(){
    cout<<"上滤"<<endl;
    HeapElemType  HeapArray[ARR_SIZE]={0,5,4,2,3,6};
    int n=5;
    printHeapArr(HeapArray,n);
    shiftUp(HeapArray,n);
    printHeapArr(HeapArray,n);

    cout<<"下滤"<<endl;
    HeapElemType  HeapArraySec[ARR_SIZE]={0,1,5,2,3,4};
    n=5;
    printHeapArr(HeapArraySec,n);
    shiftDown(HeapArraySec,1,n);
    printHeapArr(HeapArraySec,n);

    cout<<"排序"<<endl;
    HeapElemType  HeapArraySort[ARR_SIZE]={0,1,4,2,3,5,6};
    n=6;
    printHeapArr(HeapArraySort,n);
    heapsort(HeapArraySort,n);
    printHeapArr(HeapArraySort,n);

    system("pause");
}