【数据结构排序算法篇】----堆排序【实战演练】

作为一名对技术充满热情的学习者，我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代，我远非专家，而是一位不断追求进步的旅行者。通过这篇博客，我想分享我在某个领域的学习经验，与大家共同探讨、共同成长。请大家以开放的心态阅读，相信你们也会在这段知识之旅中找到启示。

前言

继续继续继续，今天我们还是排序算法，认识新的排序算法----堆排序

一、什么是堆排序

堆排序是一种基于比较的排序算法，它利用二叉堆这种数据结构的特性来对元素进行排序。二叉堆是一个近似完全二叉树的数据结构，它分为两种类型：

1. 最大堆：任何一个父节点的值都大于或等于它的孩子节点的值。
2. 最小堆：任何一个父节点的值都小于或等于它的孩子节点的值。

在堆排序算法中，最大堆用于升序排序，而最小堆则用于降序排序。下面是堆排序算法的基本步骤：

1. 建立堆：将待排序的数组构造成一个最大堆（升序排序）。这个步骤是将数组转换成最大堆的过程，通常可以从最后一个非叶子节点开始向上进行调整。
   
2. 堆排序：

• 从堆中逐个取出元素进行排序；
• 每一次将根节点（即当前最大值）与堆中最后一个元素交换，并对剩余的堆结构进行调整，重建最大堆；
• 这个过程一直重复，直到堆中仅剩下一个元素，排序完成。

堆排序过程的伪代码如下：

function heapSort(arr):
    n = length(arr)
    
    # 构建最大堆
    for i from n/2 - 1 down to 0:
        heapify(arr, n, i)
    
    # 一个一个地从堆顶取出元素
    for i from n - 1 down to 0:
        # 将当前根节点，也就是最大值移动到数组末尾
        swap arr[0] with arr[i]
        
        # 在减小堆的大小后，恢复堆的性质
        heapify(arr, i, 0)
# 将一个数组转换成最大堆
function heapify(arr, n, i):
    largest = i    # 初始化最大为根节点
    l = 2 * i + 1  # 左子节点
    r = 2 * i + 2  # 右子节点
    
    # 如果左子节点大于根节点
    if l < n and arr[l] > arr[largest]:
        largest = l
    
    # 如果右子节点大于最大目前节点
    if r < n and arr[r] > arr[largest]:
        largest = r
    
    # 如果最大值不是根节点，则进行交换
    if largest != i:
        swap arr[i] with arr[largest]
        
        # 递归地定义子堆为最大堆
        heapify(arr, n, largest)

堆排序的时间复杂度是O(nlogn)，其中n是数组的长度。这是因为创建最大堆的过程是O(n)，而从最大堆中取出每个元素进行排序的过程是O(logn)的（因为需要进行堆调整），这样的操作需要进行n次。堆排序是一个不稳定的排序算法，但是它的优势在于不需要额外的存储空间（原地排序）。

二、练习

用堆排序堆下面数组进行排序（最大堆）

int[] arr = {3, 5, 1, 6, 4, 7, 2};

堆排序的详细步骤如下：

第一步：构建最大堆

我们需要将数组转换成最大堆。我们从最后一个非叶子节点开始（即数组中间位置的节点），到根节点位置进行调整。对于给定数组，最后一个非叶子节点的索引是 (arr.length - 1) / 2。

1. (7 - 1) / 2 = 3 -> 第3个位置的元素 6 开始调整，确保它的子树遵循最大堆的性质。因为它的孩子 4 和 7 已经满足最大堆的性质（7 > 6 > 4），所以不必调整。
   
2. 接下来是位置2的元素 1，现在我们需要调整以确保子树满足最大堆性质。1 需要和它的孩子 6 和 4 中较大的一个交换，即 6。交换后的数组如下：
   int[] arr = {3, 5, 6, 1, 4, 7, 2};
   
3. 现在是位置1的元素 5。它的孩子节点是 1 和 4，都已满足最大堆的性质，不必调整。
   
4. 最后，我们调整根节点位置0的元素 3。它与两个子节点 5 和 6 中的较大者（6）交换位置。交换后的数组如下：
   int[] arr = {6, 5, 3, 1, 4, 7, 2};
   
5. 然后因为 3 换到了索引2的位置，需要继续向下调整，将 3 与其子节点 7 交换。此时，数组变为：
   int[] arr = {6, 5, 7, 1, 4, 3, 2};
   

至此，我们构建了最大堆：

6
       / \
      5   7
     / \ / \
    1  4 3 2

第二步：进行堆排序

现在我们开始从最大堆中不断取出最大元素（堆顶）来完成排序。

1. 我们将堆顶元素 6 与最后一个元素 2 交换，然后将堆大小减一（不再考虑数组中的最后一个元素），现在的数组状态如下：
   int[] arr = {2, 5, 7, 1, 4, 3, 6};
   接下来我们需要对根节点进行堆调整，使其再次成为最大堆：

2
       / \
      5   7
     / \ / 
    1  4 3 
 [6]

1. 2 将和其子节点中的较大者 7 交换：
   int[] arr = {7, 5, 2, 1, 4, 3, 6};

7
       / \
      5   2
     / \ / 
    1  4 3 
 [6]

1. 现在，将堆顶的 7 与数组中当前的最后一个元素（现在是 3）交换：
   int[] arr = {3, 5, 2, 1, 4, 7, 6};
   堆调整后，得到：

5
       / \
      4   2
     / \ 
    1  3 
 [7, 6]

1. 将堆顶 5 与当前最后一个元素 3 交换：
   int[] arr = {3, 4, 2, 1, 5, 7, 6};
   继续调整：

4
       / \
      3   2
     /   
    1  
 [5, 7, 6]

1. 重复这个过程：

• 交换堆顶 4 与最后一个元素 1：
  int[] arr = {1, 3, 2, 4, 5, 7, 6};
  
• 调整堆变成最大堆（此时只剩两个元素，已经是最大堆状态无需调整）：
  

3
    /   
   1
 [4, 5, 7, 6]

1. 交换堆顶 3 与当前最后的 1：
   int[] arr = {1, 3, 2, 4, 5, 7, 6};
   

如上步骤操作，最终我们可以得到一个升序排列的数组：

int[] arr = {1, 2, 3, 4, 5, 6, 7};

整个过程中，我们首先建立了最大堆，然后通过不断将堆顶元素（当前最大值）放到数组末尾，并重新调整剩下的元素为最大堆的方式来进行排序。这个重建和调整堆的过程称为“堆化”（heapifying）。每次都是将堆的最大值取出，数组剩余部分重新调整成最大堆，直到整个数组成为有序。

三、堆排序有何优势

堆排序在实际应用中具有一些优势，使得它在特定情况下成为非常有用的排序算法：

1. 时间复杂度稳定：堆排序的时间复杂度非常稳定，无论是最好、最坏还是平均情况都是O(nlogn)。这意味着即使在最坏的输入情况下，堆排序的表现也是可预测的。
   
2. 空间效率：堆排序是一个原地排序算法，即排序是在输入的数组上直接进行，不需要额外的长期存储空间，只需要少量额外的内存空间来存储变量。
   
3. 没有递归开销：与快速排序和归并排序等递归排序算法不同，堆排序可以很容易地转换成迭代算法，减小或消除了递归造成的额外开销。
   
4. 适用于大数据集：由于时间复杂度和空间效率的优势，堆排序适合处理大数据集。特别是在系统有内存使用限制或者稳定性要求高的环境中，其稳定的O(nlogn)性能和原地排序特性尤为重要。
   
5. 支持动态数据：由于堆排序是基于二叉堆的，这种数据结构允许在运行时动态地添加和删除元素，而不必重新排序整个数据集。
   
6. 实现优先队列：二叉堆（尤其是最大堆和最小堆）是实现优先队列的理想数据结构。优先队列在很多算法（如Dijkstra的最短路径算法）和系统（如操作系统的任务调度器）中应用广泛，堆排序是实现这些系统的核心技术之一。
   
7. 找出最大或最小元素：由于堆排序创建了最小堆或最大堆，这让获取一个集合中的最大值或最小值变得非常高效，只需要O(1)的时间。
   

尽管堆排序有这些优势，它还是不如一些更快的排序算法（比如快速排序）在通用数据排序中受欢迎。原因包括它的比较操作比快速排序多，以及实际执行速度上的差异，尤其是在数组近乎有序时。此外，因为堆排序是不稳定的排序算法，在需要稳定排序的场合可能不适合使用。

四、Java面试题

• 面试题：实现一个通用的堆排序类，并能够支持自定义比较器，使其能够适应任何自定义数据类型的排序。
  
• 解答包括两个部分：
  

1. 实现一个最大堆或最小堆的通用类。
2. 使用这个堆类来实现堆排序，并支持自定义比较器。

这里提供了一个简易的Java代码示例，其中实现了堆排序的通用类，并含有自定义比较器接口。代码示例如下：

import java.util.Comparator;
public class HeapSort<T> {
    private Comparator<T> comparator;
    public HeapSort(Comparator<T> comparator) {
        this.comparator = comparator;
    }
    private void heapify(T[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && comparator.compare(array[left], array[largest]) > 0) {
            largest = left;
        }
        if (right < n && comparator.compare(array[right], array[largest]) > 0) {
            largest = right;
        }
        if (largest != i) {
            T swapTemp = array[i];
            array[i] = array[largest];
            array[largest] = swapTemp;
            heapify(array, n, largest);
        }
    }
    public void sort(T[] array) {
        int n = array.length;
        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        // One by one extract an element from heap
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to end
            T temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            // call max heapify on the reduced heap
            heapify(array, i, 0);
        }
    }
}

使用方式例子：

// 创建一个简单的整型比较器
Comparator<Integer> comparator = Integer::compare;
// 实例化堆排序对象
HeapSort<Integer> heapSort = new HeapSort<>(comparator);
// 创建一个需要排序的数组
Integer[] arr = {3, 5, 1, 6, 4, 7, 2};
// 执行堆排序
heapSort.sort(arr);
// 输出排序后的数组
for (int value : arr) {
    System.out.print(value + " ");
}
// 期望输出结果为 "1 2 3 4 5 6 7 "

这个面试题的复杂之处在于，它不仅要求面试者理解和实现堆排序算法本身，还需要额外实现一个可定制的比较器，这使得算法能够方便地扩展以支持任意数据类型之间的比较和排序。

请注意，实际的面试过程中，面试官可能会要求你提供更多细节，如处理可能的边界情况、错误处理等。此外，也可能会要求你针对上述代码进行测试，或者解释排序算法的时间复杂度和空间复杂度。准备充分的测试案例和理解整个算法的性能特点对面试也是很有帮助的。

五、自定义数据类型的堆排序

假设我们有一个自定义数据类型Person，其中包含name和age两个字段。我们想根据age属性对Person对象数组进行排序。以下是堆排序的实现，包括定义Person类、实现自定义的比较器以及用于堆排序的类。首先是Person类的定义：

class Person {
    String name;
    int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Person{" +
               "name='" + name + '\'' +
               ", age=" + age +
               '}';
    }
}

接下来，实现Comparator<Person>接口以对Person对象进行比较：

class PersonAgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.age, p2.age);
    }
}

最后，使用刚才定义的Person类和PersonAgeComparator来实现堆排序并对Person对象的数组进行排序。我们可以重用前面提供的HeapSort类代码，因为它是通用的：

public class Main {
    public static void main(String[] args) {
        // 创建Person对象数组
        Person[] persons = {
            new Person("Alice", 30),
            new Person("Bob", 25),
            new Person("Clara", 32),
            new Person("Dave", 20)
        };
        // 创建一个Person年龄比较器
        Comparator<Person> ageComparator = new PersonAgeComparator();
        // 实例化堆排序对象
        HeapSort<Person> heapSort = new HeapSort<>(ageComparator);
        // 执行堆排序
        heapSort.sort(persons);
        // 输出排序后的Person数组
        for (Person person : persons) {
            System.out.println(person);
        }
    }
}

执行以上代码将对Person数组按照年龄从小到大进行排序。HeapSort通用类不需要任何改变，因为它使用了Comparator<T>来比较元素，所有的特定逻辑都已被封装在比较器内。

输出会按照Person的age字段升序排列，比如：

Person{name='Dave', age=20}
Person{name='Bob', age=25}
Person{name='Alice', age=30}
Person{name='Clara', age=32}

这提供了一个根据自定义数据类型属性进行排序的示例，充分展示了如何使用自定义比较器和通用的堆排序类来对特定数据类型的对象进行排序。

总结

对排序在很多情况下并没有快速排序的效率高，我们需要对各种排序进行比较，对于堆排序的学习我们就到这里，后面我们依然会持续更新。

感谢大家抽出宝贵的时间来阅读博主的博客,新人博主,感谢大家关注点赞,祝大家未来的学习工作生活一帆风顺,加油!!!