首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    深入理解数据结构第一弹——二叉树(1)——堆

    前言: 在前面我们已经学习了数据结构的基础操作:顺序表和链表及其相关内容,今天我们来学一点有些难度的知识——数据结构中的二叉树,今天我们先来学习二叉树中堆的知识,这部分内容还是非常有意思的,下面我们就开始慢慢学习...所在位置被称为树顶或者树根都可以,下面的称为子树,其中1所在分叉称为左子树,2所在分叉成为右子树 还有一些规则如下: 对于学过离散数学的同学来说这部分知识并不难,没有学过的自己再去搜一下了解一下吧,这里只讲了一些大概内容...二、什么是堆 树里面有几个特殊的概念,例如完全二叉树和满二叉树,而堆就是完全二叉树的一种,完全二叉树就是除了最后一层外,其他层节点数达到最大 堆与普通的完全二叉树的不同在于它的大小堆的性质 大堆:树任何一个父亲...>=孩子 小堆:树任何一个父亲<=孩子 例如: 三、堆的节点结构 堆用的顺序表的结构,所以堆的节点结构与顺序表差异不大 typedef int HPDataType; typedef struct...(HP* php); //判断是否为空 bool HeapEmpty(HP* php); //算个数 int HeapSize(HP* php); 看上面的函数声明部分我们就可以看到我们每一步要实现的内容

    8410

    DS:二叉树的顺序结构及堆的实现

    = 0; } 3.12 堆的打印(测试) 我们要实现堆的打印,利用我们之前封装的函数,每获取一次堆顶元素就删除一次,直到堆删完就可以获取全部的元素了!!...下面我们来进行分析 总之任何一个堆,我们都可以通过不断地pop去实现它的顺序打印!!堆排序后面会介绍!...个学生的成绩中找到前10个分数最高的,方法就是将所有的数据放在一个数组里,直接建大堆,然后pop9次就可以找到了(pop中的向下调整算法可以使得每次pop出去的都是最大值,然后pop9次的原因是因为第10次就可以直接去获取堆顶元素即可...= "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return;...= "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen fail"); return

    11510

    【初阶数据结构篇】算法中的秩序之美:顺序二叉树——堆的进阶之路(附源码)

    实现顺序结构二叉树(堆) 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力! 点赞、收藏与分享:觉得这篇文章对你有帮助吗?...堆具有以下性质 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值; 堆总是⼀棵完全⼆叉树。...(php->arr); php->arr = NULL; php->size = php->capacity = 0; } 堆的插入 void HPPush(HP* php, HPDataType...需要调整的堆(数组) 父节点,因为出堆都是交换最后一个到栈顶,所以此处就是0 数组有效数据个数,即size– 循环结束条件:child不越界即可...顺序二叉树——堆的进阶之路(附源码)的内容啦,各位大佬有什么问题欢迎在评论区指正,您的支持是我创作的最大动力!

    17710

    【初阶数据结构】实现顺序结构二叉树->堆(附源码)

    须知 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力! 点赞、收藏与分享:觉得这篇文章对你有帮助吗?...1.1 堆的性质 • 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值; • 堆总是⼀棵完全⼆叉树。...->size); return php->arr[0]; } 2.6 获取堆有效数据个数 //获取堆中有效数据个数 size_t HPsize(HP* php) { return php->size...->arr); swap(&php->arr[0], &php->arr[php->size - 1]); --php->size; AdjustDown(php->arr, 0, php->...AdjustUp(php->arr, php->size); ++php->size; } //获取堆中有效数据个数 size_t HPsize(HP* php) { return php->

    6100

    【数据结构初阶】树+二叉树+堆的实现+堆的应用

    2.2 二叉树的性质 1.满二叉树的结点个数:2^h-1(h代表树的层数) 2.完全二叉树的结点个数:最多个数:2^h-1 最少个数:2^(h-1) 3.对于任何一棵二叉树,假设叶结点个数为n0,度为2...HeapEmpty(&heap))//利用堆顶数据,我们可以打印出来这个数组的降序内容 { printf("%d ", HeapTop(&heap));//求出topk个数据,大堆中最大的前5个数据...但是后面的元素你就没法整了,你无法找出次小的元素了就,除非你利用之前的建堆,取堆顶元素,删除堆顶元素这样一系列的步骤来获取次小的元素之外,你是没有其他办法的。...TestHeap5() { // 造数据 int n, k; printf("请输入n和k:>"); scanf("%d%d", &n, &k); srand(time(0));//生成随机数的种子 FILE...生成随机数 fprintf(fin, "%d\n", val); } fclose(fin); int* minHeap = (int*)malloc(sizeof(int) * k); FILE

    35720

    【初阶数据结构】堆排序和TopK问题

    值得注意的是这里即使是小根堆但依然不是有序的,通过小根堆我们能直接获取到的是最小值。 PS:大小堆都只是父子之间的大小关系,兄弟之间是没有大小关系的 所以下面让我们看看如何对堆进行排序。...\n"); exit(-1); } php->a = temp; php->capacity = newcapacity; } php->a[php->size] = x; php...->size++; //向上调整算法,传要调整的数组和从哪个下标child开始调 AdjustUp(php->a, php->size - 1); } HeapPush函数的内容和原来顺序表不同的是在插入新数据...#include void CreateFileName(const char* filename, int N) { FILE* pf = fopen(filename, "w")...rand() % 10000 + 1); } fclose(pf); pf = NULL; } void PrintTopK(const char* filename, int k) { FILE

    62850

    【初阶数据结构】一文讲清楚 “堆” 和 “堆排序” -- 树和二叉树(二)(内含TOP-K问题)

    堆的实现 讲完堆的基本概念之后,我就要详细的给大家讲讲堆是怎样用代码实现的,内容很丰富,希望大家能够好好看! 2.1 堆的结构体设置 我们在之前讲过了,堆是一棵完全二叉树,我们可以用顺序表来实现。...那这时有的读者就会提问了,为什么不写一个头插数据的函数和一个尾插数据的函数,而只需要写一个添加数据的函数即可? 原因就是,我们在之前反复提到,堆是一棵特别的完全二叉树。...但事实上,我不建议大家这么写。大家不妨思考一下,当parent变为0时,循环条件成立,进入循环执行循环体。...确实没有影响,删除这种位置上的数据是没有任何意义的! 既然要玩,我们就玩大的!删掉根节点。这就好比在一个黑帮中,老二觊觎老大的位置,狠不得找个机会做掉老大,总而自己主管整个黑帮。...测试结果: 到这里关于堆的内容就已经全部讲完了! 如果觉得本文写还不错的话,麻烦给偶点个赞吧!!!

    7910
    领券