数据结构与算法面试专题——堆排序

完全二叉树

完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

设计目标：完全二叉树的设计目标是高效地利用存储空间，同时便于进行层次遍历和数组存储。它的结构使得每个节点的子节点都可以通过简单的计算得到，从而实现快速的节点访问。

实现原理：完全二叉树是一棵满二叉树，除了最后一层外，每一层都被完全填充。最后一层的节点都集中在左边。这种结构可以用数组来存储，其中数组的索引对应节点的位置。例如，对于索引为i的节点，其左子节点的索引为2i+1，右子节点的索引为2i+2，父节点的索引为(i-1)/2。

优点：空间利用率高，易于实现数组存储。层次遍历简单，可以通过数组索引快速访问节点。

缺点：插入和删除节点可能比较耗时，特别是当需要保持完全二叉树的结构时，可能需要重新调整整个结构。

堆结构

堆结构就是用数组实现的完全二叉树结构

设计目标：堆结构的设计目标是实现高效的优先级队列和排序算法。它基于完全二叉树的结构，通过维护堆序性（父节点的值大于或等于子节点的值，或者小于或等于子节点的值）来实现快速的插入和删除操作。

实现原理：堆结构通常用数组来实现，其中数组的索引对应节点的位置。在堆中，每个父节点的值都满足一定的条件，例如最大堆中父节点的值大于或等于子节点的值，最小堆中父节点的值小于或等于子节点的值。插入操作通过在数组末尾添加元素，然后通过上浮（Percolate Up）来维护堆序性。删除操作通常是指删除堆顶元素，然后通过下沉（Percolate Down）来维护堆序性。

优点：插入和删除操作的时间复杂度为O(log n)，在优先级队列和排序算法中性能优越。空间利用率高，用数组实现简单。

缺点：对于范围查询等操作不友好，无法高效地进行任意元素的查找和删除操作。

如何理解“堆”？

堆本质是一种特殊的树。关于这个树，只要满足两点要求，它就是一个堆：

1. 堆是一个完全二叉树；
2. 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

第一点，堆必须是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。

第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

堆结构的heapInsert操作

将一个新元素插入到堆结构中，并维持堆的性质（即父节点的值大于或等于子节点的值，或者小于或等于子节点的值，视堆的类型而定）。

示例

假设有一个最大堆，堆数组为 [100, 85, 90, 80, 75, 70]，现在需要插入元素 95。

• 插入后数组变为 [100, 85, 90, 80, 75, 70, 95]。

• 新元素的位置是 6（从 0 开始计数）。

• 比较新元素与父节点（位置 (6-1)/2=2，值 90）：95 > 90，交换两者位置，数组变为 [100, 85, 95, 80, 75, 70, 90]。

• 继续比较新元素与新的父节点（位置 (2-1)/2=0，值 100）：95 < 100，无需交换。

• 插入完成，堆性质得以维持。

优点：能够在 O(log n) 时间复杂度内完成插入操作。

缺点：需要调整堆的结构，可能导致多次数据交换。

堆结构的heapify操作

在堆结构中，当某个节点的子节点可能违反堆的性质时，通过调整该节点及其子节点，维持堆的性质。

示例

假设有一个最大堆，堆数组为 [95, 85, 90, 80, 75, 70]，现在需要对位置 0 的节点进行 heapify 操作。

• 该节点的值为 95，子节点为 85 和 90。

• 95 大于子节点，无需调整。

• 如果堆数组为 [75, 85, 90, 80, 75, 70]，需要对位置 0 的节点进行 heapify。

• 比较子节点 85 和 90，选择较大的 90 作为候选。

• 交换 75 和 90，数组变为 [90, 85, 75, 80, 75, 70]。

• 继续 heapify 位置 2 的节点（原来的 75）。

• 比较子节点 80 和 75，交换 75 和 80，数组变为 [90, 85, 80, 75, 75, 70]。

• 继续 heapify 位置 3 的节点（原来的 75），没有子节点，调整完成。

优点：能够在 O(log n) 时间复杂度内完成调整操作。

缺点：需要遍历节点的子节点，可能导致多次数据交换。

堆结构的增大

当堆中的元素数量增加，需要扩展堆的存储空间。

• 通常使用动态数据结构，如动态数组或链表，来实现堆的动态增长。

• 当需要增大堆时，分配新的内存空间，并将原堆中的元素复制到新空间中。

示例

假设堆当前的存储数组大小为 10，已满。需要插入一个新元素，堆将自动增大到大小为 20。

堆结构的减少

当堆中的元素数量减少，可能需要缩小堆的存储空间，以节省内存。

• 释放堆中多余的存储空间，调整存储数组的大小。

• 可以通过动态数据结构的特性，如动态数组的收缩功能，实现堆的缩小。

示例

假设堆当前的存储数组大小为 20，但只有 5 个元素。可以将堆缩小到大小为 10，释放多余的空间。

优先级队列结构

设计目标

优先级队列的设计目标是允许高效地访问和操作优先级最高的元素。与普通队列中的先进先出（FIFO）原则不同，优先级队列中的元素根据其优先级进行排序，并且优先级最高的元素会被优先处理。

实现原理

优先级队列通常使用堆结构来实现，能够高效地维护元素的优先级顺序。

1. 插入操作（Enqueue）

将新元素添加到堆的末尾。

通过上浮（Percolate Up）操作，将新元素与父节点进行比较和交换，直到满足堆的性质。

2. 删除操作（Dequeue）

删除堆顶元素（优先级最高的元素）。

将堆的最后一个元素移动到堆顶。

通过下沉（Percolate Down）操作，将该元素与子节点进行比较和交换，直到满足堆的性质。

优点

插入和删除操作的时间复杂度为 O(log n)，在需要动态维护优先级的场景中性能优越。

空间利用率高，可以用数组实现，节省存储空间。

缺点

不支持高效的随机访问和查询操作，无法快速找到任意元素。

对于某些操作（如批量插入），可能需要重新构建整个堆，导致较高的开销。

堆排序

堆排序是一种原地的、时间复杂度为O(n log n)的排序算法。

堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。

实现步骤

1. 先让整个数组都变成大根堆结构，建立堆的过程: 

   1. 从上到下的方法，时间复杂度为O(N * logN) 

   2. 从下到上的方法，时间复杂度为O(N) 

2. 把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N * logN) 

3. 堆的大小减小成0之后，排序完成

实现代码

    /*** 对给定的整数数组进行堆排序。* 堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为O(N log N)，空间复杂度为O(1)。** @param arr 待排序的整数数组*/public void heapSort(int[] arr) {// 如果数组为空或者长度小于2，直接返回，因为不需要排序if (arr == null || arr.length < 2) {return;}// O(N*logN)// 从数组的最后一个元素开始，依次将每个元素调整为大根堆for (int i = arr.length - 1; i >= 0; i--) {heapify(arr, i, arr.length);}// 初始化堆的大小为数组的长度int heapSize = arr.length;// 将堆顶元素（最大值）与堆的最后一个元素交换，并将堆的大小减1swap(arr, 0, --heapSize);// O(N*logN)// 当堆的大小大于0时，继续进行排序while (heapSize > 0) { // O(N)// 将堆顶元素调整为大根堆heapify(arr, 0, heapSize); // O(logN)// 将堆顶元素（最大值）与堆的最后一个元素交换，并将堆的大小减1swap(arr, 0, --heapSize); // O(1)}}/*** 将指定索引位置的元素插入到堆中，并调整堆结构，使其满足大根堆的性质。* 该方法会将新元素与其父节点比较，如果新元素大于父节点，则交换它们的位置，* 并继续向上比较，直到新元素小于等于父节点或到达堆顶。** @param arr   包含堆元素的数组* @param index 要插入的元素的索引*/public void heapInsert(int[] arr, int index) {// 当当前元素大于其父节点时，交换它们的位置，并更新当前元素的索引while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}/*** 调整指定索引位置的元素，使其满足大根堆的性质。* 该方法会将指定元素与其子节点比较，如果该元素小于其子节点中的最大值，* 则交换它们的位置，并继续向下比较，直到该元素大于等于其子节点或到达叶子节点。** @param arr      包含堆元素的数组* @param index    要调整的元素的索引* @param heapSize 当前堆的大小*/public void heapify(int[] arr, int index, int heapSize) {// 计算左孩子的下标int left = index * 2 + 1; // 当左孩子存在时，继续循环while (left < heapSize) { // 两个孩子中，谁的值大，把下标给largest// 1）只有左孩子，left -> largest// 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest// 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest// 找出左右孩子中值较大的那个的下标int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;// 比较父节点和较大孩子的值，将较大值的下标赋给largestlargest = arr[largest] > arr[index] ? largest : index;// 如果父节点已经是最大的，跳出循环if (largest == index) {break;}// 交换父节点和较大孩子的位置swap(arr, largest, index);// 更新当前节点的下标index = largest;// 计算新的左孩子的下标left = index * 2 + 1;}}/*** 交换数组中两个指定索引位置的元素。** @param arr 包含元素的数组* @param i   第一个元素的索引* @param j   第二个元素的索引*/public void swap(int[] arr, int i, int j) {// 使用临时变量交换两个元素的值int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

过程分析

我们可以把堆排序的过程大致分解成两个大的步骤，建堆和排序。

建堆

我们首先将数组原地建成一个堆。所谓“原地”就是，不借助另一个数组，就在原数组上操作。建堆的过程，有两种思路。

第一种是在堆中插入一个元素。尽管数组中包含个数据，但是我们可以假设，起初堆中只包含一个数据，就是下标为1的数据。然后，我们调用插入操作，将下标从2到n的数据依次插入到堆中。这样我们就将包含n个数据的数组，组织成了堆。

第二种实现思路，跟第一种截然相反。第一种建堆思路的处理过程是从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。而第二种实现思路，是从后往前处理数组，并且每个数据都是从上往下堆化。

逐层调整，直到整个数组满足堆的条件。

• 从最后一个非叶子节点开始，逐层向上进行 heapify 操作。
• 最后一个非叶子节点的索引为：floor((n-2)/2)，其中 n 是数组的长度。
• 使用 heapify 调整以该节点为根的子树。

排序

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为n的位置。

当堆顶元素移除之后，我们把下标为n的元素放到堆顶，然后再通过堆化的方法，将剩下的n－1个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是n一1的位置，一直重复这个过程，直到最后堆中只剩下标为1的一个元素，排序工作就完成了。

为什么快速排序要比堆排序性能好？

堆排序数据访问的方式没有快速排序友好

快速排序的数据访问方式：

• 快速排序是基于分治法（Divide and Conquer）的排序算法。它通过选择一个基准值（pivot），将数组划分为两个子数组，左侧子数组的元素小于或等于基准值，右侧子数组的元素大于或等于基准值。然后递归地对这两个子数组进行排序。在分割过程中，快速排序对数组中的元素进行连续的比较和交换，这种操作在内存中的数据访问模式通常是连续的，与现代计算机的缓存机制非常匹配。连续的内存访问使得缓存命中率更高，减少了内存访问的延迟，从而提高了排序的效率。

• 例如，当对一个已部分排序的数组进行快速排序时，基准值的选择和分割操作会使得数组被分割为较小的子数组，而这些子数组在内存中是连续存储的。对这些子数组进行递归排序时，缓存能够有效地预取（cache prefetch）这些连续的数据，减少了从主存中加载数据的次数，加快了排序的速度。

堆排序的数据访问方式：

• 堆排序依赖于堆数据结构，需要频繁地访问父节点和子节点。在堆排序过程中，数据的访问模式是随机的，无法充分利用内存的局部性原理。堆的父节点和子节点在内存中可能不是连续存储的，因此访问这些节点时，常常会导致缓存未命中。缓存未命中会增加内存访问的延迟，降低排序的效率。

• 例如，在调整堆结构时，需要比较父节点和子节点的值，并根据比较结果进行交换。这种访问模式使得数据在内存中的跳转较为频繁，无法像快速排序那样利用缓存的预取特性，导致性能下降。

对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序

快速排序的数据交换次数：

• 快速排序的平均时间复杂度为O(n log n)，其数据交换次数相对较少。在快速排序的分割过程中，每个元素会被交换到正确的位置，但整个过程中交换的次数通常比堆排序少。快速排序的递归结构使得大部分元素的比较和交换发生在较小的子数组中，减少了不必要的数据移动。

• 例如，对一个随机分布的数组进行快速排序时，每次分割操作会使得元素被快速地放置在接近其最终位置的地方。这减少了后续排序过程中需要移动的数据量，从而降低了数据交换的总次数。

堆排序的数据交换次数：

• 堆排序的主要操作是构建堆和调整堆结构。在构建堆的过程中，需要多次比较和交换元素。每次插入或删除元素时，堆结构的维护需要进行多次比较和交换，以确保父节点的值大于或等于子节点的值（对于最大堆而言）。在堆排序的整个过程中，数据交换的次数相对较多。

• 例如，当构建一个最大堆时，每个元素都需要与它的子节点进行比较和交换。如果一个元素的值小于它的子节点中的较大者，就需要交换它们的位置，并继续对子节点进行调整。这个过程会涉及到多次数据交换，直到堆的性质被满足。在堆排序的调整过程中，这样的交换操作会频繁发生，导致数据交换次数增加，从而影响了排序的性能。