第23章：堆进阶
你认为你已经掌握了堆的知识？在本章中，你将探索与堆有关的四个不同问题。这些问题的作用是巩固你对数据结构的基本知识。
挑战1: 找出第n个最小的整数
写一个函数，找出未排序数组中第n个最小的整数。例如。
let integers = [3, 10, 18, 5, 21, 100] 。
如果n=3，结果应该是10。
挑战2：分步走图
给出以下数组，直观地构建一个最小堆。提供如何构建最小堆的分步图。
[21, 10, 18, 5, 3, 100, 1]
挑战3：结合两个堆 写一个结合两个堆的方法。
挑战4：最小堆？
写一个函数，检查一个给定的数组是否是最小堆。
解决方案
挑战1的解决方案
解决未排序数组中第n个最小整数的方法有很多。例如，你可以选择本章所学的排序算法，对数组进行排序，然后抓取第n个索引处的元素。
让我们来看看如何使用min堆获得第n个最小的元素!
我们来看看这个解决方案。
-
用未排序的数组初始化一个min堆。
-
current跟踪第n个最小的元素。
-
只要堆不是空的，就继续删除元素。
-
从堆中移除根元素。
-
检查你是否达到了第n个最小的元素。如果是，则返回该元素。
-
如果不是，则递增电流。
-
如果堆是空的，返回nil。
建立一个堆需要O(n)。从堆中移除每个元素需要O(log n)。请记住，你也在做这个动作n次。总的时间复杂度是O(n log n)。
挑战2的解决方案
[21, 10, 18, 5, 3, 100, 1]
挑战3的解决方案
将此作为Heap.swift的一个附加函数。
合并两个堆是非常直接的。你首先合并两个数组，这需要O(m)，其中m是你要合并的堆的长度。构建堆需要O(n)。总的来说，该算法的运行速度为O(n)。
挑战4的解决方案
要检查给定的数组是否是最小堆，你只需要通过二进制堆的所有父节点。为了满足最小堆的要求，每个父节点必须小于或等于其左、右子节点。
下面是抓取给定父节点索引的左右子节点索引的辅助方法。
现在让我们看看如何确定一个数组是否是一个最小堆。
-
如果数组是空的，那么它就是一个min堆!
-
以相反的顺序遍历数组中的所有父节点。
-
获得左和右的子节点索引。
-
检查左边的元素是否小于父元素。
-
检查右边的索引是否在数组的范围内，并检查右边的元素是否小于父元素。
-
如果每个父子关系都满足min-heap属性，则返回true! 这个解决方案的时间复杂度是O(n)。这是因为你仍然需要遍历数组中的每个元素。
| 上一章 | 目录 | 下一章 |
|---|