特殊的数据结构-堆.pptx

特殊的数据结构-堆.pptx **堆** 是一种特殊的数据结构，它以二叉树的形式存在，但在计算机内存中通常以数组的形式被实现。堆主要用于解决需要快速访问或删除最高优先级元素的问题，比如在计算机科学中，它常用于实现**优先队列**。 在我们的游乐场游戏中，问题转化为建立一个**最小优先队列**，其中每次需要取出并删除优先级最高的元素，即数组中最小的元素。传统的队列遵循“先进先出”（FIFO）原则，而最大优先队列则要求“最大优先级的元素先出”。线性的存储结构，无论是无序还是有序，都无法高效地满足这一需求。为了解决这个问题，我们引入了**堆**。 **堆** 有两种主要类型：**最大堆** 和 **最小堆**。最大堆保证每个节点的值大于或等于其子节点的值，而最小堆则保证节点的值小于或等于子节点的值。这两种堆都必须是**完全二叉树**，这意味着除了最后一层外，每一层都被完全填满，并且所有节点尽可能地靠左放置。 在数组表示中，堆的根节点位于索引1的位置，其左子节点在索引2的位置，右子节点在索引3的位置，以此类推。堆的性质可以归纳为： 1. **堆性质**：最大堆中，每个节点的值不小于其子节点的值；最小堆中，每个节点的值不大于其子节点的值。 2. **完全二叉树**：所有叶子节点都在同一层或相邻两层，且叶子节点尽可能地靠左。 3. **父节点与子节点的关系**：父节点的索引是子节点索引除以2向下取整，反之，子节点的索引是父节点索引的2倍（左子节点）或2倍加1（右子节点）。 堆的主要操作包括： 1. **向上调整（ShiftUp）**：当一个节点的值大于其父节点时，通过交换节点位置使其回到正确位置，直到满足堆性质或成为新的根节点。 2. **向下调整（ShiftDown）**：当删除根节点后，将最后一个节点移到根位置，然后通过与子节点比较并交换，确保堆的性质得到保持。 3. **插入新节点（Insert）**：将新节点添加到堆的末尾，然后通过向上调整恢复堆性质。 4. **删除根节点（Delete）**：删除根节点，将最后一个节点移到根位置，然后进行向下调整。 5. **建堆**：可以通过自顶向下或自底向上的方式构建堆，例如，从一组无序数据中构建堆，可以先将数据放入数组，然后从最后一个非叶子节点开始，逐个调整节点以满足堆性质。 堆的这些操作，尤其是插入和删除，都具有较高的效率。在最大堆或最小堆中，插入一个新元素的时间复杂度是O(log n)，删除根元素的时间复杂度也是O(log n)，这是因为调整操作通常涉及的树的高度是log n。 堆的应用广泛，包括在**堆排序**算法中，以及在操作系统中管理内存的**内存分配器**，在数据库索引中也有应用，如**B树**和**B+树**等。在优先队列的实现中，堆是一种非常有效的数据结构，因为它能在常数时间内提供最大或最小元素，而插入和删除操作也相对高效。