堆数据结构与堆排序的个人理解

关于堆排序，已经研究了整整一个星期，不论是从网络论坛CSDN或者图书馆书籍中，都获益匪浅，但是知识内容都是差不多的，如何理解是自己的。这里我就写一下自堆排序的认识。

首先要弄清楚的观点是：

1、堆是一种数据结构

通常来说，一种数据结构所必备的操作有三个：初始化，插入数据，删除数据。堆也不例外。因此一旦我们写出了数据结构的基本操作，我们可以将其封装起来，用于其它的地方。比如可以用堆这种数据结构来进行其它的排序操作的实现。上升只看父节点，下降只看儿子。

2、本文中堆的存储是基于顺序数组的

因为数组的实现可以是链式或者顺序，这里实现的时候是一般情况，就是基于顺序数组的，使用顺序数组来存储堆的内容。

其中会用到的一个交换两个元素的小函数：

数据结构中的：
插入方法：
我们每次思考插入方法的时候，堆中的数据都是从数组的最后一个元素插入的。因此每次在插入一个元素以后，这个数组不再满足一个堆的条件，因此要恢复堆，基本思想就是将插入的值a[i]与他的父亲比较，再决定是否交换两者的值，一直循环，直到堆顶，直观上来看，就是新插入的元素，由堆底像堆顶上升的过程：
删除方法：
按照堆的定义，堆中每次都只能删除第0个数据。因此为了便于恢复堆，实际的操作是将最后一个数据的数据的值赋值给根的结点，然后再从根的结点开始进行一次从上向下的调整。调整时现在左右儿子中找最小的，如果父亲结点比这个最小的还要小，说明不需要调整。反之，交换两者，继续考虑其父亲。其过程相当于，从根结点将一根数据下沉的过程。

 初始化：
初始化有两种产生最小堆的方法：一个是利用Fixdown，另外一个是利用Fixup；
void main(){int arr[]={0,1,5,4,2,7,6,8};//MakeMinHeap1(arr,8);MinheapsortTodescendarray(arr,8);for (int i=0;i<8;i++){printf("%d ",arr[i]);}printf("\n");MakeMinHeap1(arr,8);for (int i=0;i<8;i++){printf("%d ",arr[i]);}printf("\n");        MakeMinHeap2(arr,8);for (int i=0;i<8;i++){printf("%d ",arr[i]);}printf("\n");}