数据结构意义

定义并维护一种结构，这个结构能让我们在特定的工作场景下更简单高效地解决问题。

胡光老师: 定义一种性质，维护这种性质

我们牢记每一种数据结构的性质，那么思路就清晰了，不要太死扣是用什么实现的。

数据结构最有价值的是对我们思维逻辑结构的改变，而不是实现在程序中的代码。

image.pngimage.png
image.pngimage.pngimage.png

xue.kaikeba.com/static/xxx.mp4

缓存
CPU 取数据 内存快 硬盘慢
先从缓存找，找不到再到硬盘找
image.png
image.pngimage.pngimage.png

什么情况下 需要虚拟头 ？

链表头地址可能发生改变 才去考虑 虚拟头部

队列

任务队列，任务缓存区
image.png

树

image.png
链表是特殊的树。链表只有一个指针域，树有多个（数组指针域）。
image.pngimage.pngimage.pngimage.pngimage.png

注意这个 计算式和记录式
计算地址还是记录地址 一个是节省空间 一个是节省时间。

image.png
左右孩子编号规律有这种性质有什么好处：不需要记录子树的地址 可以节省大量存储空间

image.png

树结构为什么重要

树的节点 => 集合
边 => 关系
这样我们得出，父节点是一个集合，子节点是两个或多个互不相交的子集。

树也适合各种场景下的查找操作

学习二叉树的作用image.png

数学归纳法的三步：K0 正确 => 假设 ki 是正确的 => k(i +1) 正确

image.png

任何一个多叉树都可以转化为二叉树：就是下面的左孩子右兄弟表示法。

下面的左边的黑背景图就是 alpha go 的注释代码。用这个节省空间地用2叉树表示n叉树

具体节省了多少

n 个节点的 k 叉树
有效指针域 (n - 1) 全部指针域 k n
浪费的指针域 (k - 1) n + 1
k 越大 浪费的空间越多

image.png

左孩子右兄弟 还可以让二叉树表示森林

为什么节省空间：因为多叉树需要多个指针域

左图是 alpha go 的代码 就是用 二叉树表示了n叉树

完全二叉树 （节省空间）

胡光 课程 - 图25

编号为 i 的子节点：左孩子编号 2 i； 右孩子编号 2 i + 1

所以每一个节点都不需要两个指针域去存储孩子的位置，非常节省空间！

它也是堆的基础结构

堆 heap

左边为我们抽象出来的思维逻辑数据结构（好理解）
右边为实际数据存储的结构（在内存中）。

image.png

堆是一种基于完全二叉树的结构

大顶堆：其中任意一个三角结构的根节点都大于其两个子节点。那么最顶部是最大值
小顶堆：反之

性质：兄弟之间没有大小关系规定，但是父子节点是有大小关系

思考：第三大的值在哪儿，可能在第二层或第三层
第四大的值可能在第 2，3，4层，由此推导

image.png

头部弹出（向下调整），尾部添加（向上调整）。

堆排序

image.png

堆 —— 优先队列

为什么把堆也叫做优先队列 ?

  1. 入堆从尾部入，出堆从头部出。这个性质上和队列 相同。
  2. 每次出堆时，都是最大的元素或者最小的元素出，我们可以理解成优先级最高的元素先出，所以堆又叫优先队列

但是，与其说优先队列是堆的一个别名，更准确地，堆是优先队列的一种实现方式。

image.png

堆 干什么

image.png

题目及答案堆与优先队列-0409.pdf

例题1：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

可以用堆来解决，维护一个大小为 k 的大顶堆

例题2: https://leetcode-cn.com/problems/last-stone-weight/

‘二维’的堆，打开新世界，船长灵泛的脑子

例题3: https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/

灵活运用 compare 前k个高频单词 根据题意思考后做了点下优化

例题4: https://leetcode-cn.com/problems/top-k-frequent-words/

丑数 Ⅱ

例题5

image.png

堆内存和数据结构堆之间的关系是什么？

老婆饼和老婆的关系