数据结构

2024-07-16 10:13| 来源: 网络整理| 查看: 265

一. 堆🌲

1. 堆的概念

2. 堆的存储方式

二. 堆的基本操作🌳

1. 创建堆，向下调整与向上调整

2. 堆的插入(offer）

3. 堆的删除(poll)

三. 堆的应用🌴

1. 堆排序（从小到大排）

2. top-k问题

一. 堆🌲

1. 堆的概念

堆（heap）：一种有特殊用途的数据结构——用来在一组变化频繁（发生增删查改的频率较高）的数据集中查找最值。

堆在物理层面上，表现为一组连续的数组区间：long[] array ；将整个数组看作是堆。

堆在逻辑结构上，一般被视为是一颗完全二叉树。

满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆；反之，则是小堆，或者小根堆，或者最小堆。当一个堆为大堆时，它的每一棵子树都是大堆。

2. 堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储；

假设 i 为结点在数组中的下标，则有：

💖 如果 i 为0，则 i 表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2；

💖 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子；

💖 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子。

二. 堆的基本操作🌳 1. 创建堆，向下调整与向上调整

创建堆只有两种堆可以创建，要不就是大根堆，要不就是小根堆。而要满足大根堆还是小根堆的逻辑，就要向下调整的操作才能实现。要想自己实现堆，堆本身就是一个数组，因此创建一个数组来创建堆。

对于集合 { 27,15,19,18,28,34,65,49,25,37 } 中的数据，如果将其创建成堆呢？

仔细观察上图后发现：根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可。向下过程(以小堆为例)：

1️⃣. 让 parent 标记需要调整的节点，child 标记 parent 的左孩子(注意：parent 如果有孩子一定先是有左孩子)

2️⃣. 如果 parent 的左孩子存在，即: child < size，进行以下操作，直到 parent 的左孩子不存在：

⏩看 parent 右孩子是否存在，存在找到左右孩子中最小的孩子，让 child 进行标

⏩将 parent 与较小的孩子 child 比较，如果：

parent 小于较小的孩子 child，调整结束；

否则：交换 parent 与较小的孩子 child，交换完成之后，parent 中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即 parent = child;child = parent*2+1;然后继续2️⃣。

public class HeapTest { /** * 小堆的向下调整，要求满足向下调整的前提 * @param array 堆所在的数组 * @param size 前 size 个元素视为堆中的元素 * @param index 要调整位置的下标 */ public static void shiftDown(long[] array, int size, int index) { // 只要看到 int 类型的，基本就是下标或者个数，不是元素 // 这里直接 while(true)即可 // while (2 * index + 1 < size) { 如果这么写，下面就不用再进行叶子的判断 while (true) { // 1. 判断 index 所在位置是不是叶子 // 逻辑上，没有左孩子一定就是叶子了（因为完全二叉树这个前提） int left = 2 * index + 1; if (left >= size) { // 越界 -> 没有左孩子 -> 是叶子 -> 调整结束 return; // 循环的出口一：走到的叶子的位置 } // 2. 找到两个孩子中的最值【最小值 via 小堆】 // 先判断有没有右孩子 int right = left + 1; // right = 2 * index + 2 int min = left; // 假设最小值就是左孩子，所以 min 保存的最小值孩子所在的下标 if (right < size && array[right] < array[left]) { // right < size 必须在 array[right] < array[left] 之前，不能交换顺序 // 因为先得确定有右孩子，才有比较左右孩子的意义 // 有右孩子为前提的情况下，然后右孩子的值 < 左孩子的值 min = right; // min 应该是右孩子所在的下标 } // 3. 将最值和当前要调整的位置进行比较，判断是否满足堆的性质 if (array[index] 0) { // 如果双亲比孩子大，parent满足堆的性质，调整结束 if (array[parent] > array[child]) { break; } else{ // 将双亲与孩子节点进行交换 int t = array[parent]; array[parent] = array[child]; array[child] = t; // 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增 child = parent; parent = (child - 1) / 1; } } } 3. 堆的删除(poll)

具体如下：（注意：堆的删除一定删除的是堆顶元素。）

1️⃣. 将堆顶元素对堆中最后一个元素交换；

2️⃣. 将堆中有效数据个数减少一个；

3️⃣. 对堆顶元素进行向下调整；

public long poll() { // 返回并删除堆顶元素 if (size < 0) { throw new RuntimeException("队列是空的"); } long e = array[0]; // 用最后一个位置替代堆顶元素，删除最后一个位置 array[0] = array[size - 1]; array[size - 1] = 0; // 0 代表这个位置被删除了，不是必须要写的 size--; // 针对堆顶位置，做向下调整 shiftDown(array, size, 0); return e; } 三. 堆的应用🌴 1. 堆排序（从小到大排）

一个数组根据从小到大排序，要创建大堆来排；一个数组根据从大到小排序，要创建小堆来排。

此处就以创建大堆为例。首先将堆顶的元素和堆中的最后一个元素交换，交换后再向下调整，调整后再与堆的倒数第二个元素进行交换。

public void HeapSort() { int end = usedSize-1; while(end>0) { int tmp = elem[0]; elem[0] = elem[end]; elem[end] = tmp; shiftUp(0,end); end--; } } 2. top-k问题

若要从N个数字中取得最小的K个数字，则需要创建大小为K的大堆来获取。若要从N个数字中取得最大的K个数字，则需要创建大小为K的小堆来获取。

拜托，面试别再问我TopK了！！！_架构师之路-CSDN博客

【本文地址】

公司简介

联系我们