福州做网站需要多少钱,网站建设要准备什么资料,北京网站开发网站建设报价,canva ppt模板引入
要学习堆#xff0c;首先要先简单的了解一下二叉树#xff0c;二叉树是一种常见的树形数据结构#xff0c;每个节点最多有两个子节点#xff0c;通常称为左子节点和右子节点。它具有以下特点#xff1a;
根节点#xff08;Root#xff09;#xff1a;树的顶部节…引入
要学习堆首先要先简单的了解一下二叉树二叉树是一种常见的树形数据结构每个节点最多有两个子节点通常称为左子节点和右子节点。它具有以下特点
根节点Root树的顶部节点没有父节点。子节点Children每个节点最多有两个子节点分别称为左子节点和右子节点。叶子节点Leaf没有子节点的节点称为叶子节点。父节点Parent每个节点都有一个父节点除了根节点。深度Depth从根节点到某个节点的唯一路径的长度根节点的深度为0。高度Height从某个节点到它的最远叶子节点的路径长度叶子节点的高度为0。遍历Traversal遍历二叉树是指按照一定顺序访问树中的每个节点常见的遍历方式包括前序遍历、中序遍历和后序遍历。
二叉树的应用非常广泛在后面我会详细介绍。
满二叉树除了叶子结点外每个结点都有两个子结点 一个深度为k的满二叉树有2的k次方减一个节点。
完全二叉树除了最底层可能不是满的外其它每一层从左到右都是满的。 满二叉树是完全二叉树的子集满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。 堆就是一种完全二叉树。
二叉树的储存
逻辑结构和物理结构
逻辑结构和物理结构是计算机科学中两个重要的概念它们描述了数据在计算机中的不同组织方式。 逻辑结构 逻辑结构是指数据元素之间的相互关系和操作规则。它关注的是数据之间的逻辑关联而不考虑数据在计算机内部的存储方式。常见的逻辑结构包括线性结构、树形结构和图形结构。线性结构中的数据元素之间是一对一的关系例如线性表、栈、队列等。树形结构中的数据元素之间存在一对多的关系例如二叉树、B树等。图形结构中的数据元素之间是多对多的关系例如图、网络等。 物理结构 物理结构描述了数据在计算机内部存储的方式和组织形式也称为存储结构。物理结构与计算机的存储器相关它包括了数据元素在内存中的存储位置和存储方式。常见的物理结构包括顺序存储结构和链式存储结构。顺序存储结构是将数据元素连续地存储在内存中的一块连续的存储空间中例如数组。链式存储结构是通过指针将数据元素存储在内存中的不同位置并通过指针将它们串联起来例如链表。
逻辑结构关注数据之间的逻辑关系和操作规则而物理结构关注数据在计算机内部的实际存储方式和组织形式。
二叉树的储存
二叉树有多种存储方式常见的包括顺序存储和链式存储。 顺序存储 顺序存储通常使用数组来表示二叉树。假设树的根节点存储在数组下标为0的位置则对于任意一个下标为i的节点 其左子节点的下标为2i 1其右子节点的下标为2i 2 例如如果要存储二叉树的节点值为[1, 2, 3, 4, 5, 6, 7]的完全二叉树可以使用数组[1, 2, 3, 4, 5, 6, 7]进行存储。 链式存储 链式存储则是通过节点之间的引用来表示二叉树的结构每个节点包含数据域和左右子节点指针域。
链式储存我们放在后边更新在这里我们先学习顺序储存。
顺序储存
顺序储存用数组来储存顺序存储一般只适合用来存储完全二叉树堆用顺序储存再存储非完全的二叉树会存在空间浪费 堆的实现 头文件
#define _CRT_SECURE_NO_WARNINGS 1#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int HPDatatype;typedef struct Heap
{HPDatatype * a;int size;int capacity;}HP;//初始化
void HPInit(HP* php);//插入数据
void HPPush(HP* php, HPDatatype x);//交换
void Swap(HPDatatype* a,HPDatatype * b);//销毁
void HPDestroy(HP* php);//向上调整
void AdjustUp(HPDatatype* a, int child);//向下调整
void AdjustDown(HPDatatype* a,int n, int parent);//删除顶部数据
void HPPop(HP* php);//返回顶部数据
HPDatatype* HPTop(HP* php);//判空
bool HPEmpty(HP* php);
实现文件
#define _CRT_SECURE_NO_WARNINGS 1
#include Heap.h// 初始化
void HPInit(HP* php)
{assert(php);php-a NULL;php-capacity php-size 0;}//插入数据
void HPPush(HP* php, HPDatatype x)
{assert(php);//判断空间够不够if (php-capacity php-size){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDatatype* tmp (HPDatatype* )realloc(php-a,newcapacity * sizeof(HPDatatype));if (tmp NULL){perror(realloc fail);exit(-1);}php-capacity newcapacity;php-a tmp;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}//交换
void Swap(HPDatatype* a, HPDatatype* b)
{HPDatatype cmp *a;*a *b;*b cmp;
}//销毁
void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}//向上调整
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 2 * parent 1;//先假设左边的小while (child n){if (child 1 n a[child 1] a[child])//规避chlid 1 越界的风险{child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child 2 * parent 1;}else{break;}}}//删除顶部数据
void HPPop(HP* 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(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}//判空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}
TOP-K问题
一般来说堆分为两类 大堆Max Heap在最大堆中每个节点的值都大于或等于其子节点的值。换句话说堆顶部的元素是整个堆中的最大值。最大堆常用于实现优先队列其中具有最高优先级的元素始终位于堆顶。 小堆Min Heap在最小堆中每个节点的值都小于或等于其子节点的值。因此堆顶部的元素是整个堆中的最小值。最小堆也常用于优先队列其中具有最低优先级的元素位于堆顶。
简单来说大堆中同一个分支中大的在上小堆中同一分支小的在上。
在这里以小堆为例
向上调整算法
往堆中插入一个数据时先将插入的数据放到堆的最后一个节点然后利用向上调整算法依次调整。
图示 只要子节点不越界循环一直进行当字节点不小于父节点时跳出if()语句进入else跳出循环。
//向上调整
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;}}
}求一堆数据(储存在小堆中)中最最小的前几个数据将数据插入堆中小堆的堆顶中储存的就是堆中最小的数据把堆顶的数据取下来再将堆顶的数据释放用向上调整算法调整堆再依次取堆顶重复。
//TOP-K
void HPtest02()
{int a[] { 5,6,1,4,2,8 };HP s;HPInit(s);for (size_t i 0; i sizeof(a) / sizeof(int); i){HPPush(s, a[i]);}int k 0;scanf(%d, k);while (k--){printf(%d , HPTop(s));HPPop(s);}HPDestroy(s);
}int main()
{HPtest02();return 0;
} 演示 在TOP-K问题中我们会发现输出的数据是按顺序拍好的那么我们可不可以在此基础上进行排序呢。 把数据储存到堆中之后再依次拿出来。
//排序
void HPtest03()
{int a[] { 5,6,1,4,2,8 };HP s;HPInit(s);for (size_t i 0; i sizeof(a) / sizeof(int); i){HPPush(s, a[i]);}int i 0;while (!HPEmpty(s)){a[i] HPTop(s);HPPop(s);}HPDestroy(s);
}
int main()
{HPtest03();return 0;
}
这样我们就可以对数据进行排序。 这个算法的时间复杂度非常低 。 一个有k个节点的对的深度为logk一条分支最多交换log (k) - 1次所以 算法的时间复杂度为log N。 但是这并不能称作真正的排序因为它在原数组的基础上开辟了新的空间。 堆排序
建堆算法
//堆排序
void HeapSort(int* a, int n)
{//建堆for (int i 1; i n; i){AdjustUp(a, i);}
}void Heaptset()
{int a[] { 5,6,8,4,1,2,3 };HeapSort(a, 7);
}
int main()
{//HPtest01();/*HPtest02();*///HPtest03();Heaptset();return 0;
} 排序
在惯性思维中要排降序应该会建大堆排升序会建小堆。但这样会导致一个问题以建排降序 为建小堆为例 小堆的堆顶为这组数据中最小的数我们将它取出作为排序的第一个数 取出堆顶后找出第二小的数据 但是此时的堆各个节点已经不满足之前的大小关系了4之前是6和5的父节点比6和5大但是与2为兄弟节点兄弟节点之间的大小关系原来并不清楚无法直接找出第二大的数据可以重新把剩下的数据建堆但是没必要时间成本大。在堆排序中不能让第一个数据直接拿出去这样会改变节点之间的父子关系不能确定大小关系无法找出需要的节点。
接下来以排降序排降序为例演示过程。
//堆排序
void HeapSort(int* a, int n)
{//建堆for (int i 1; i n; i){AdjustUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}void Heaptset()
{int a[] { 5,6,8,4,1,2,3 };HeapSort(a, 7);
}
int main()
{//HPtest01();/*HPtest02();*///HPtest03();Heaptset();return 0;
}
调试 向下调整算法的时间复杂度为log N,堆排序在最坏的情况下N个数据要排N次所以堆排序的时间复杂度为N log N。可以极大的提高程序的效率。
