【数据结构与算法】之堆及其实现！

1、堆的概念及结构

2、堆的实现

2.1 堆向下和向上调整算法

2.2 堆的创建

2.3 建堆时间复杂度

2.4 堆的插入

2.5 堆的删除

2.6 完整代码

3、完结散花

                                                     个人主页：秋风起，再归来~

                                                        数据结构与算法

   个人格言：悟已往之不谏，知来者犹可追

           克心守己，律己则安！

1、堆的概念及结构

如果有一个关键码的集合K = { ，，，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：且 = 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

2、堆的实现

2.1 堆向下和向上调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

代码实现：

1、向上调整算法：

//交换
void swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//先假设做孩子小int child = parent * 2 + 1;while (child < size)//当孩子超过最后一个叶子时结束循环{if ((child + 1 < size) && a[child + 1] < a[child])//如果右孩子小于左孩子,右孩子与父亲比较{child++;}if (a[child] < a[parent])//建小堆，即小的当父亲{swap(&a[child] , &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

2、向下调整算法

//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//先假设做孩子小int child = parent * 2 + 1;while (child < size)//当孩子超过最后一个叶子时结束循环{if ((child + 1 < size) && a[child + 1] < a[child])//如果右孩子小于左孩子,右孩子与父亲比较{child++;}if (a[child] < a[parent])//建小堆，即小的当父亲{swap(&a[child] , &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

2.2 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

//建堆算法一（从第一个孩子向上调整）
//这种写法的时间复杂度为n*logn
//for (int i = 1; i < len; i++)
//{
//	AdjustUp(a, i);//从第一个孩子向上调整建堆
//}
// 
//建堆算法二（从倒数第一个根向下调整）
//这种写法的时间复杂度为O(N)[更优]
for (int i = (len - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(a, len, i);//从倒数第一个根向下调整建堆
}

2.3 建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：向下调整建堆的时间复杂度为O(N)。

2.4 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{//先判断容量大小是否足够if (hp->_size == hp->_capacity){int newcapacity = hp->_capacity == 0 ? hp->_capacity = 4 : hp->_capacity * 2;//如果原来没有空间，就给上4，有的话就扩大为原来的两倍HPDataType* ptr = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));//动态扩容if (ptr == NULL){perror("realloc fail;");return;}//也可以用assert断言一下hp->_a = ptr;//开辟成功将地址传给arrhp->_capacity = newcapacity;//更新容量}//对堆进行插入操作hp->_a[hp->_size] = x;hp->_size++;//插入一个数据后就进行向上调整，保证堆的结构AdjustUp( hp->_a,  hp->_size-1);
}

2.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

// 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(hp->_size > 0);//先交换根与叶子的位置，保证根的左右都是堆，方便后面的根先下调整swap(&hp->_a[0], &hp->_a[hp->_size - 1]);//再删除最后一个数据，即是堆的最小或最大值hp->_size--;AdjustDown(hp->_a, hp->_size, 0);
}

2.6 完整代码

Heap.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;
//堆的初始化
void HeapInit(Heap* hp);// 堆的销毁
void HeapDestory(Heap* hp);// 堆的插入
void HeapPush(Heap* hp, HPDataType x);// 堆的删除
void HeapPop(Heap* hp);// 取堆顶的数据
HPDataType HeapTop(Heap* hp);// 堆的数据个数
int HeapSize(Heap* hp);// 堆的判空
bool HeapEmpty(Heap* hp);

Heap.c

#include"Heap.h"//堆的初始化
void HeapInit(Heap* hp)
{assert(hp);hp->_a = NULL;hp->_capacity = hp->_size = 0;
}// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp->_a);hp->_a = NULL;hp->_capacity = hp->_size = 0;
}//交换
void swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while(child>0){if (a[child] < a[parent])//< 建小堆；> 建大堆{swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{//先判断容量大小是否足够if (hp->_size == hp->_capacity){int newcapacity = hp->_capacity == 0 ? hp->_capacity = 4 : hp->_capacity * 2;//如果原来没有空间，就给上4，有的话就扩大为原来的两倍HPDataType* ptr = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));//动态扩容if (ptr == NULL){perror("realloc fail;");return;}//也可以用assert断言一下hp->_a = ptr;//开辟成功将地址传给arrhp->_capacity = newcapacity;//更新容量}//对堆进行插入操作hp->_a[hp->_size] = x;hp->_size++;//插入一个数据后就进行向上调整，保证堆的结构AdjustUp( hp->_a,  hp->_size-1);
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//先假设做孩子小int child = parent * 2 + 1;while (child < size)//当孩子超过最后一个叶子时结束循环{if ((child + 1 < size) && a[child + 1] < a[child])//如果右孩子小于左孩子,右孩子与父亲比较{child++;}if (a[child] < a[parent])//建小堆，即小的当父亲{swap(&a[child] , &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(hp->_size > 0);//先交换根与叶子的位置，保证根的左右都是堆，方便后面的根先下调整swap(&hp->_a[0], &hp->_a[hp->_size - 1]);//再删除最后一个数据，即是堆的最小或最大值hp->_size--;AdjustDown(hp->_a, hp->_size, 0);
}// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(hp->_size > 0);return hp->_a[0];
}// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp->_size;
}// 堆的判空
bool HeapEmpty(Heap* hp)
{assert(hp);return hp->_size == 0;
}