堆和栈的区别
1.分配方式不同
- 栈有静态分配和动态分配，且均由系统自动分配
- 堆都是动态分配，需要程序员申请和释放
2.申请大小限制不同
- 栈是向栈底扩展，一般是连续的内存区域，大小固定（可以通过ulimit-a查看，ulimit-s修改）
- 堆向高地址扩展，是不连续的内存区域，大小灵活调整
3.申请效率不同
- 栈由系统分配，速度快，不会有碎片
- 堆由程序员分配，速度慢，且会有碎片
栈像去饭馆吃饭，只要点菜和吃，其余不用管
堆像自己做菜，自由度大，但是吃完要善后
队列和栈的区别
1.数据存储方式
- 队列先进先出
- 栈先进后出
2.操作方式
- 队列元素从前端出队，后端入队
- 栈顶部弹出，顶部压入
链表：链表是一种线性数据结构，由一系列的元素（或称为节点）组成
优点：
- 高效的插入和删除:头部插入O(1),中间插入O(N)
- 动态大小
- 无需连续内存块，更灵活利用内存
缺点：
- 因为存储位置不是连续的，随机访问的效率低
- 查找元素要遍历整个链表，时间复杂度高，O(N)
哈希表
查找和增删的效率均为0(1)
哈希碰撞：不同的键映射到同一个值就会引起哈希碰撞
- 拉链法：讲冲突的元素存储在链表中
- 线性探测法：保证tablesize大于datasize，继续寻找下一个空位来存放信息
数组
数组是一种线性数据结构，用于存储元素的集合，其中每个元素都可以通过其索引来进行访问
- 固定大小：大多数编程语言中的数组（如C++、Java等）在声明时需要固定大小，并且后续不能改变。但某些语言（如Python中的list）提供了动态数组的实现，可以调整大小。
- 随机访问：由于数组元素在内存中是连续存储的，所以可以通过索引直接快速访问任意元素。
- 高效的访问速度：对于读取元素操作，数组可以提供O(1)的时间复杂度。
- 低效的插入和删除：在数组的中间位置插入或删除元素需要移动元素，因此这些操作的时间复杂度为O(n)。
七种排序方法：
1.快速排序：O(NlogN)
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复过程，直到所有元素都排列到相应位置
2.直接插入排序：O(N ^ 2)
将需要排序的数据按其关键码值的大小逐个插入到一个已经排序好的有序序列中直到所有数据插入完为止，得到一个新的有序序列。
3.希尔排序：O(N ^ 1.3 - N ^ 2)
先选定一个整数，把待排序文件中所有记录分成个组，所有距离相同的数据分在同一组内，并对每一组内的数据进行直接插入算法排序。然后重复上述分组和排序的工作，直到分成一组，算法结束
4.直接选择排序：O(N ^ 2)
每一次在待排序的数据元素中选出最小的一个元素（或者每一次在待排序的数据元素中选出最大的一个元素），存放在序列中的起始位置，知道全部待排序的数据元素排序完
5.堆排序:O(N * logN)
堆可以分为两种类型：最大堆和最小堆。在最大堆中，父节点的值大于或等于其子节点的值；在最小堆中，父节点的值小于或等于其子节点的值。堆排序通常使用最大堆来实现
- 建堆： 将未排序的数组构造成一个最大堆。这可以通过从数组的中间开始到第一个元素结束，对每个元素进行下沉操作来实现。
- 堆顶与末尾元素交换： 此时，最大堆的根节点（堆顶）是整个堆中的最大元素。将其与堆的最后一个元素交换，这样最大的元素就位于了数组的末尾。
- 调整堆： 由于交换后，根节点可能不再满足最大堆的性质，因此需要将其进行下沉操作，重新调整为最大堆。
- 重复上述步骤： 去掉已经排序的最后一个元素（之前的最大元素），然后重复步骤2和步骤3，直到堆中只剩下一个元素。
6.冒泡排序:O(N ^ 2)最差
每次遍历待排序数组，对相邻进行比较，按照要求小向前移动，大向后移动
7.归并排序:O(N * logN)
即先使每个子序列有序，再使子序列间有序，若将两个有序表合并成一个有序表，称为二路归并。
跳表：
底层是链表实现，用于存储一个有序的元素集合，允许快速的查找，插入和删除元素，其时间复杂度是0(logn)
基本思想是采用多级链表来表示有序集合。在这种结构中，每一层都是前一层的一个子集，并且只有最底层包含所有的元素。
或，异或，非，或非
或：任一为1则是1
异或：两位不同则为1，相同则为0
非：取反
四叉树
四叉树（Quadtree）是一种常用于二维空间分割和数据组织的数据结构。它将二维空间递归地划分成四个象限（或子节点），从而形成一个树状结构。四叉树通常用于空间索引、图像处理、地理信息系统（GIS）、碰撞检测等领域，因为它可以有效地处理具有空间关联性的数据。
四叉树的特点和用途包括：
- 空间分割：四叉树将空间分割成四个相等的子区域，然后每个子区域再进一步划分。这种递归划分可以用于快速查找某个点或对象所在的区域，以及在这些区域中执行各种操作。
- 图像压缩和处理：四叉树可以用于图像的压缩和处理。在图像中，每个节点代表一个区域，可以统计该区域内的像素颜色信息，从而实现图像的压缩和分析。
- 碰撞检测：在计算机游戏和模拟中，四叉树可以用于检测物体之间的碰撞。通过将空间分割成子区域，可以减少需要检测的对象数量，提高碰撞检测的效率。
- 地理信息系统（GIS）：四叉树可以用于存储地理数据，如地图信息、地点坐标等。这有助于快速查找特定地理区域内的数据。
四叉树的基本操作包括插入、删除、查找、遍历等。根据具体的应用和要求，还可以扩展四叉树以适应不同的数据结构和查询需求。此外，还有八叉树（Octree）、kd-树（kd-tree）等其他树状数据结构，它们在不同的情况下可能更适合特定的问题。
总之，四叉树是一种灵活且强大的数据结构，可用于解决多种涉及空间和分割的问题。