数据结构堆的实现（C语言）

概念

        堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

        1、堆中某个结点的值总是不大于或不小于其父结点的值。

        2、堆总是一棵完全二叉树。建议不了解完全二叉树概念的先去学一下完全二叉树。

        根结点的值最大的堆叫做大根堆或者最大堆，根结点的值最小的堆叫做小根堆或者最小堆。

        堆是一种非线性结构，是完全二叉树的一种特殊形式，他符合完全二叉树的所有性质。一般使用数组来表示，虽然使用顺序存储结构很难表示出树的父子结点之间的关系，但是完全二叉树是个例外，将完全二叉树的结点按从上到下、从左到右的顺序进行编号，对应数组下标，是可以用数组进行表示的。父子结点的下标对应关系如下：

        若序号从0开始，设一个结点的的下标为i，其父结点的下标为(i - 1) / 2，左孩子结点下标为i * 2 + 1，右孩子结点下标为 i * 2 + 2。

        例如上图的小根堆，他的数组存储结构如下：

        1的左孩子结点为i * 2 + 1 = 1，右孩子结点为i * 2 + 2 = 2。6的父结点为(i - 1) / 2，左孩子结点为i * 2 + 1 = 3，右孩子结点为i * 2 + 2 = 4。

        例如上图的大根堆，他的数组存储结构如下：

        10的父结点为(i - 1) / 2，左孩子结点为i * 2 + 1 = 3，右孩子结点为i * 2 + 2 = 4。

        堆的操作包括创建、插入、删除、返回堆顶元素、摧毁等，下述操作均以大根堆为例。小根堆的操作和大根堆类似。

 堆的创建

        要创建一个堆，首先要明确其数据结构类型，我们使用的是顺序存储结构也就是数组作为存储结构，堆的结构体定义和初始化如下：

typedef int ElemType;typedef struct heap
{ElemType *datas;int size;int capacity;
}*max_heap;max_heap heap_init(int max_size)
{//申请堆结构体的内存max_heap heap = (max_heap)malloc(sizeof(struct heap));//申请数组的内存heap->datas = (ElemType *)malloc(max_size * sizeof(ElemType));//初始化当前元素个数为0heap->size = 0;//初始化堆的最大存储空间heap->capacity = max_size;//返回堆结构体指针return heap;
}

 堆的插入

        堆插入的基本思想是每次插入都是将先将新数据放在数组最后，由于从这个新数据的父结点到根结点必然为一个有序的序列，现在的任务是将这个新数据插入到这个有序序列中，使其符合堆的特性，这就类似于直接插入排序中将一个数据并入到有序区间中，这也就是堆的向上调整方法。

        我们以下图中的大根堆为例，插入一个元素new_data。

         将new_data插入到数组的最后位置。

        根据new_data的数值不同会有多种情况，以下分情况讨论：

        情况一：若new_data为3，我们可以看到从15-6-3，依然是一个有序序列，且符合大根堆的父子结点关系。插入完成。

        情况二：若new_data为9，我们可以看到15-6-9，就不是一个有序序列，也不符合大根堆的关系，这时候我们就需要将6和new_data进行互换，交换之后的15-9-6，就满足大根堆的特性了。

        情况三：若new_data为23，可以看到15-6-23，也不符合大根堆特性，将6和new_data互换，15-23-6仍然不符合特性，那么就再将其互换，23-15-6就符合大根堆的特性。

//在堆中插入一个元素
bool heap_insert(max_heap heap,ElemType data)
{//如果堆满则返回falseif(heap->size == heap->capacity)return false;int i = heap->size;//当前插入位置，数组的最后//判断其父结点的值是否大于data，若不大于data，则将父结点下移，再判断其父结点的父结点，类似于直接插入排序while(heap->datas[(i - 1) / 2] < data && i > 0){//将当前结点的父结点下移heap->datas[i] = heap->datas[(i - 1) / 2];//更新当前结点i = (i - 1) / 2;}//最终i就是正确的插入位置。heap->datas[i] = data;//堆中元素个数+1heap->size++;return true;
}

堆的删除

        堆中每次都只能删除堆顶元素。删除了堆顶元素之后就要对堆进行重建，重新补充堆顶元素，此时就将数组最后的元素移动到根结点，然后再从根结点开始进行一次从上到下的调整。先判断孩子结点是否比根结点大，若孩子结点都比根结点小，则不需要调整，若孩子结点比根结点大，则要在孩子结点中挑出一个大的进行互换，因为大根堆的堆顶元素是最大的，之后依次向下调整，直到结点没有孩子结点为止。

        以下图中的大根堆为例，删除其堆顶元素。

        删除之后用数组末尾的元素补充。 

        之后进行大根堆的向下调整过程，根结点的两个孩子结点都比它大，应该挑两个中的最大，所以将10和4互换位置。 

        继续比较4的孩子结点，两个孩子结点都比4大，所以再挑两个中的最大，将4和8互换位置。

        最后发现4已经没有孩子结点，向下调整结束。最终符合大根堆特性。 

bool heap_delete(max_heap heap)
{//判断堆是否为空if(heap->size == 0)return false;//堆中元素个数-1heap->size--;//从根结点开始向下调整int i = 0;while(1){int left = i * 2 + 1;//记录左孩子结点int right = i * 2 + 2;//记录右孩子结点int max_child = left;//默认最大为左孩子//找到最大孩子,当右孩子存在且比左孩子大时修改为右孩子，否则默认为左孩子if(right < heap->size && heap->datas[right] > heap->datas[left])max_child = right;//若最大孩子不存在（主要是为了防止左孩子）或者该结点比最大孩子还大，则跳出循环if(max_child >= heap->size || heap->datas[heap->size] > heap->datas[max_child])break;//将最大孩子结点上移heap->datas[i] = heap->datas[max_child];//当前结点向下移动i = max_child;}//插入到正确位置heap->datas[i] = heap->datas[heap->size];return true;
}

堆的构建

        堆的构建是将已经存在的N个元素按最大堆/最小堆的要求存放在一个一维数组中。后续的堆排序会用到这种方法。

        方法一：通过插入操作，将N个元素一个接一个相继插入到一个初始为空的堆中，时间复杂度最大为O(NlogN)。

int main(int argc, char const *argv[])
{max_heap heap;heap = heap_init(20);int array[10] = {5,6,15,84,65,352,45,32,145,56};for (int i = 0; i < 10; i++){heap_insert(heap,array[i]);}//将数组元素从下标0开始全部打印出来heap_printf(heap);heap_destory(heap);return 0;
}

         程序将插入之后的数组按下标顺序全部打印出来，运行结果如下：

        乍一眼看着打印的内容好像并不符合大根堆的特性，那么我们根据打印结果将其转换为完全二叉树之后如下图，可以看出是符合大根堆的特性的。 

        方法二：在线性时间复杂度下建立最大堆/最小堆

        1、先将N个元素按输入顺序存入，使其先满足完全二叉树的结构特性。

        2、再调整各结点位置，使其满足最大堆/最小堆的有序特性。

        步骤一显而易见非常简单，就是一个数组的赋值过程，难重点在于步骤二调整结点位置，如果我们从根结点开始调整，使用向下调整的方法，但是这个二叉树本身就是乱序的，他不符合堆的特性，因此无法向下调整，那么我们只能从下开始向上调整。

        从下开始调整并不意味着从数组的最后一个元素开始，叶子结点根本就没有子树，他本身无论如何都是一个堆，也就没有调整的必要，所以要从有孩子结点的结点开始调整，使该子树符合堆的特性，直至根结点，最终使整个二叉树符合堆的特性。

        下面以一个大小为10的数组为例，int array[10] = {5,6,15,84,65,352,45,32,145,56};先将其填入到一个完全二叉树中。

        之后从数组的末尾开始，过滤掉叶子结点，第一个需要调整的就是65这个结点，判断65和56,65 > 56，所以不需要移动，56是叶子结点，所以进行下一个。继续调整84这个结点，他的最大孩子结点为145,145 > 84，则需要调整84和145的位置，其子结点也是叶子结点，所以进行下一个。

        15的最大孩子结点为352，352 > 15，需要交换，他的子结点是叶子结点，所以进行下一个。

        6的最大孩子结点是145,145 > 6，需要交换，他的孩子结点不是叶子结点，所以需要继续判断。

        交换之后的6的最大孩子结点是84，84 > 6，需要交换，其孩子结点为叶子结点，所以进行下一个。

        最后到了调整根结点，其最大孩子结点为352，352 > 5，需要交换，其孩子结点不是叶子结点，需要继续判断。

        交换之后的5的最大孩子结点为45，需要交换，其孩子结点为叶子结点，所以判断完成。

        最终整个二叉树完全符合了堆的特性。

//两种的区别就在于移动，注释掉的是采用临时变量，将两个结点进行交换
//未注释的掉的是使用类似直接插入排序的方法，和堆的删除相同
void heap_creat(max_heap heap,ElemType *data,int size)
{for (int i = 0; i < size; i++){heap->datas[i] = data[i];}heap->size = size;for(int i = size - 1;i >= 0;i--){int j = i;int tmp = heap->datas[i];while (1){int left = j * 2 + 1;//左孩子结点int right = j * 2 + 2;//右孩子结点int max_child = left;//默认大的为左孩子结点//若右孩子存在且右孩子比左孩子大则修改max_child为rightif(right < size && heap->datas[right] > heap->datas[left])max_child = right;//若最大孩子不存在，说明已经到了叶子结点//或者该结点已经比最大孩子还大，符合堆的特性，则跳出循环if(max_child >= size || tmp > heap->datas[max_child])break;//将最大孩子结点上移heap->datas[j] = heap->datas[max_child];j = max_child;}heap->datas[j] = tmp;}
}