陈塘庄网站建设,网站建设内容和功能的介绍,广州网站推广,手机模板网站模板下载工具一、堆的概念
在提出堆的概念之前#xff0c;首先要了解二叉树的基本概念
一颗二叉树是节点的有限集合#xff0c;该集合#xff1a;
1、或者为空#xff1b;
2、或者由一个根节点加上两颗分别称为左子树和右子树的两颗子树构成#xff1b; 堆就是一颗完全二叉树…一、堆的概念
在提出堆的概念之前首先要了解二叉树的基本概念
一颗二叉树是节点的有限集合该集合
1、或者为空
2、或者由一个根节点加上两颗分别称为左子树和右子树的两颗子树构成 堆就是一颗完全二叉树
堆有两种小堆和大堆
堆在内存上的存储是数组形式的物理结构我们认为想象成链式结构逻辑结构
通过数组结构去实际存储有这样的规律每个父节点的下标乘以2加1就是左孩子节点加2就是右孩子节点无论是左孩子还是右孩子其下标减去1再 /2 就是父节点的下标这就是通过数组存储堆完全二叉树的优点。 二、堆实现的相关头文件
#includestdio.h
#includeassert.h
#includestdbool.h
#includestdlib.h
#includeerrno.h
//堆有两种大堆、小堆
typedef int HPDataType;typedef struct Heap
{HPDataType* arr;int size;int capacity;
}Heap;//堆的构建
void HeapInit(Heap* php);//堆的销毁
void HeapDestroy(Heap* php);//向上调整
void AdjustUp(Heap* php, int child);
//堆的插入
void HeapPush(Heap* php, HPDataType x);//向下调整
void AdjustDown(Heap* php, int parent, int size);
//堆的删除
void HeapPop(Heap* php);//取出堆顶的数据
HPDataType HeapTop(Heap* php);//堆的数据个数
int HeapSize(Heap* php);//堆的判空
bool HeapEmpty(Heap* php);
堆是完全二叉树所以用数组存储可以方便访问子节点和父节点 三、堆基本接口的实现大堆
1、堆的构建初始化
void HeapInit(Heap* php)
{assert(php);php-arr NULL;php-size php-capacity 0;
}2、堆的销毁
//堆的销毁
void HeapDestroy(Heap* php)
{assert(php);if (php-arr NULL){free(php-arr);}php-arr NULL;php-size php-capacity 0;
}
3、堆的插入
void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-arr,sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(realloc failed);exit(1);}php-arr tmp;php-capacity newcapacity;}php-arr[php-size] x;//向上调整AdjustUp(php-arr,php-size-1);
}
堆只有大堆和小堆之分插入数据和顺序表一样关键是插入数据之后要对数组里面的数据进行调整
插入数据用到向上调整
//向上调整
void AdjustUp(HPDataType* arr,int child)
{int parent (child - 1) / 2;while (child0){if (arr[child] arr[parent]){//交换数组里面的值Swap(arr[child], arr[parent]);//继续比较大小要将child和parent的值向上移动child parent;parent (child - 1) / 2;}else{//之前的数据都是一个一个建好的大堆//父节点的值比子节点的大停止break;}}
}
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp *x;*x *y;*y tmp;
}
每次插入进堆的数据都是孩子节点形参名称向上调整的原因就是每个子树的父亲节点理论上是要大于孩子节点的但是插入的数据可能要比父节点大所以在向上调整函数里面要先通过孩子节点的下标找到对应的父节点之后再比较看是否要交换直到父亲节点大于子节点
循环结束的条件是child0当child为0的时候说明已经调整到根节点的位置了。
4、堆的删除
//堆的删除
void HeapPop(Heap* php)
{assert(php php-size0);//删除是删除的是堆顶的数据若是直接让数组整体往前移动 堆被打乱 要重新建堆 时间复杂度高//方法交换堆首位的数据让size--再从堆顶开始向下调整Swap(php-arr[0], php-arr[php-size - 1]);php-size--;AdjustDown(php-arr, 0, php-size - 1);
}
堆的删除删除的是根节点的数据也就是数组里面下标为0的数据如果直接移动数组下标删除那么新数组就不再是一个堆此时要重新建堆代价过大
采用这种方式每次进行删除之前先交换堆首尾的数据之后再让size--就访问不到原来的根节点此时得到的新数组除了根节点处的数据它的子树都是大堆此时进行向下调整算法把这个不应该是根节点的数据向下调整把下面的数据里面最大的调整到根节点处
向下调整算法
void AdjustDown(HPDataType* arr, int parent, int size)//size指向的是最后一个有效数据
{int child parent * 2 1;//定义为左孩子while (child size){if (child1size arr[child] arr[child 1])//当最后一个子树只有左孩子时child1越界{child child 1;//若是右孩子较大那么就定义成右孩子}//总是大的调到上面去if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}
向下调整是从下标为0处开始调整的这个0下标位置就是父节点通过乘以2加上1的办法找到子节点但是要找到子节点里面较大的那个所以上面代码就有了child处和child1处数据大小的比较若是父节点小于子节点就交换每次调整完都刷新父节点和子节点的下标以便一直往下面调整直到父节点的数据要大于子节点的数据就停止
循环结束的条件是childsize这里的size是数组里面最后一个有效数的下标
5、堆顶数据、堆的数据个数、堆的判空
//取出堆顶的数据
HPDataType HeapTop(Heap* php)
{assert(php php-size0);return php-arr[0];
}//堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php-size;
}//堆的判空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}
