[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");
}

 

相关推荐

Leave a Comment