数据结构二叉树--堆（数据结构实现和堆排序的一种实现）

堆是一个数据结构

逻辑结构：完全二叉树（要求父节点大于孩子节点或者小于孩子节点）

存储结构：顺序存储

typedef int DataType;
typedef struct Heap{DataType*data;int size;int capacity;
}Heap;void InitHeap(Heap*pH)
{assert(pH);pH->data=NULL;pH->size=0;pH->capacity=0;
}void expand(Heap*pH)
{DataType*p=realloc(pH->a,sizeof(DataType)*(pH->capacity+2));if(p==NULL){printf("%s",strerror(errno));    }pH->data=p;pH->capacity+=2;
}void Swap(int*n1,int*n2)
{int tmp=*n1;*n1=*n2;*n2=tmp;
}void AdjustUp(Heap*pH,int child)
{while(child>0){int parent=(child-1)/2;if(data[child]<data[parent]){Swap(&data[child],&data[parent]);child=parent;}else{break;}}
}void HeapPush(Heap*pH,int n)
{assert(pH);expand(pH);pH->data[pH->size++]=n;AdjustUp(pH->data,pH->size-1);
}void AdjustDown(DataType*data,int parent,int size)
{int child=2*parent+1;while(child>n&&child+1>n){if(data[child]>data[child+1]){child+=1;}if(data[parent]>data[child]){Swap(&data[parent],&data[child]);parent=child;child=2*parent+1;}}}void HeapPop(Heap*pH)
{assert(pH->size);Swap(&pH->data[0],&pH->data[pH->size-1]);pH->size--;AdjustDown(pH->data,0,pH->size);
}

这是堆的基本操作，我们如果有一个数组，想借助堆这个数据结构利用额外的空间来实现排序，那么先依次将数据放入堆中，再依次删除并将删除的数据放入到数组中完成排序。每一次插入的时间复杂度最多都是O（logN），删除也一样，比起之前冒泡排序O（n^2）要好一些。

但是有很大的缺点，首先就是要有一个堆，每次都先这样实现堆很麻烦，还有一点是空间复杂度为O(N)，有额外开辟的空间。我们可以这样做:用一个指针从左到右依次扫描数组，向上调整算法的使用前提是本身为堆，那我们从下标为1的元素开始，扫描到一个相当于插入了一个，然后用向上调整算法调整为堆，再扫描下一个+调整，扫描完最后一个元素为止。那么这个数组就是一个堆了，如果我们想升序排列，则整理为大堆，先找最大的数据放在最后，如果想降序排列就先找最小的，也就是小堆。why？如果我们排列升序，先找最小的，那么后面的元素怎么办？需要重新整理成堆，时间复杂度为N^2*logN，这比N^2的时间复杂度还要高，没必要搞这么一堆出来了，所以排升序找最大的。排成堆+交换就找出了最大的，然后排成堆+交换就找出了次大的，以此类推即可。这个做法的本质就是在一个数组上模拟堆的插入和删除，扫描增加一个就是插入，交换一次就是删除。