公司想做个网站,微信应用平台开发,爱你视频免费观看,企业网站的常见类型有什么#x1f339;个人主页#x1f339;#xff1a;喜欢草莓熊的bear #x1f339;专栏#x1f339;#xff1a;数据结构 目录
前言
一、堆的实现
1.1 堆的向下调整算法
思路#xff1a;
1.2 堆的向上调整算法
1.3 堆的创建
1.4 堆的复杂度计算
向下调整建堆的复杂度… 个人主页喜欢草莓熊的bear 专栏数据结构 目录
前言
一、堆的实现
1.1 堆的向下调整算法
思路
1.2 堆的向上调整算法
1.3 堆的创建
1.4 堆的复杂度计算
向下调整建堆的复杂度 向上调整建堆的复杂度
1.5 堆的插入
1.6 堆的删除
1.7 堆的代码实现
总结 前言 在上期内容介绍了二叉树、还简单提了一下堆的概念和大堆、小堆。回顾一下堆是首先是完全二叉树因为是完全二叉树所以使用数组储存比较合理。 一、堆的实现
1.1 堆的向下调整算法 现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。 给上一个例子 int arr[] {27,15,19,18,28,34,65,49,25,37}; 上面这幅图就是向下调整的算法的过程图
思路 假设我们通过向下调整算法建立小堆我们就需要从根的左右子树开始比较得出左右子树小的那一个和根比较谁小谁就是根。我们之前还介绍父亲节点和孩子节点的概念我们这里就要使用到。根据我们上面的思路向下调整算法需要通过比较还在节点后进行调整。所以我们需要知道父亲节点然后再找到孩子节点为什么要知道父亲节点呢我们通过数组储存着堆下标就可以帮助我们找到孩子节点。 大致思路就是这样我们来写代码
void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp *x;*x *y;*y tmp;
}void ADjustDown(HPDataType* a, int n,int parent)//向下调整
{int child parent * 2 1;while (child n){//假设法if (a[child] a[child 1] child 1 n)//比较左右子树找到较小的子树。{child;}if (a[parent] a[child])//数据交换{Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
} 解释一下个别代码child 1 n 防止数组越界。
1.2 堆的向上调整算法 向上调整我们需要从最后一层向上调整所以我们是通过孩子节点得到父亲节点。大致思路和向下调整一样比较孩子节点的大小后再和父亲节点比较一直比较到根节点。根据child parent *21 反推得到 parent child -1 /2 。
直接上代码
void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp *x;*x *y;*y 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;}}
}
1.3 堆的创建 下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。 给上一个例子 int a[] {1,5,3,8,7,6}; 1.4 堆的复杂度计算 因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值多几个节点不影响最终结果) 向下调整建堆的复杂度 向上调整建堆的复杂度
是O(N) N * logN 得到方法和向下调整一样推导就可以了。
1.5 堆的插入 先插入一个 10 到数组的尾上再进行向上调整算法直到满足堆。 堆的插入需要用的向上调整
1.6 堆的删除 删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 1.7 堆的代码实现
堆的初始化、销毁都是很简单和之前写的栈啊等等都十分相似。剩下一些 获取堆顶元素、堆的个数、堆的判断都比较简单就不讲解了给上了代码。
typedef int HPDataType;typedef struct Heap//因为堆的定义就是满二叉树与完全二叉树用数组储存非常好。
{HPDataType* a;//数组int size;int capacity;
}Heap;//小堆情况下的初始化
void HPInit(Heap* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}//销毁
void HPDestory(Heap* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp *x;*x *y;*y 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 ADjustDown(HPDataType* a, int n,int parent)//向下调整
{int child parent * 2 1;while (child n){//假设法if (a[child] a[child 1] child 1 n){child;}if (a[parent] a[child]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//入堆
void HPPush(Heap* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity){int Newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, Newcapacity * sizeof(HPDataType));if (tmp NULL){perror(ralloc fail);return;}php-a tmp;php-capacity Newcapacity;}php-a[php-size] x; ADjustUp(php-a,php-size - 1);
}//出堆消除堆顶数据
void HPPop(Heap* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;ADjustDown(php-a,php-size,0);
}//取堆顶数据
HPDataType HPTop(Heap* php)
{assert(php);assert(php-size 0);return php-a[0];
}//堆的数据个数
int HPSize(Heap* php)
{assert(php);return php-size;
}//堆的判空
bool HPEmpty(Heap* php)
{assert(php);return php-size 0;
} 总结 本节重点堆的向上、向下调整算法的代码实现 和 复杂度计算。
