每日一道算法题：堆排序详解

引言

堆排序是一种高效的排序算法，时间复杂度为O(nlogn)，其核心是堆数据结构。本文将详细介绍堆的定义、性质、堆排序的实现、优化以及其应用和变种。

堆的定义与性质

推的定义与性质

推是一种特殊的完全二叉树，满足以下两个性质：

• 父节点的值大于或者等于子节点的值，称之为大根堆。
• 父节点的值小于或者等于子节点的值，称之为小根堆。

堆的定义与性质

堆是一种基于推的数据结构，通常把大根推简称为堆。堆满足以下性质：

• 堆是一棵完全二叉树。
• 堆中每个节点的值都必须满足堆的性质。

堆排序详解

建堆

大根堆

大根堆中父节点的值大于等于它的子节点的值，建立大根堆的过程是从最后一个非叶子节点开始，依次向上调整堆。下面是建立大根堆的代码实现：

private void adjustHeap(int[] arr, int i, int len) {
    int temp = arr[i];
    for (int j = 2 * i + 1; j < len; j = 2 * j + 1) {
        if (j + 1 < len && arr[j] < arr[j + 1]) {
            j++;
        }
        if (arr[j] > temp) {
            arr[i] = arr[j];
            i = j;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

public void buildMaxHeap(int[] arr, int len) {
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
}

小根堆

小根堆中父节点的值小于等于它的子节点的值，建立小根堆的过程与建立大根堆过程类似，只需将相应的判断符号反转即可。下面是建立小根堆的代码实现：

private void adjustHeap(int[] arr, int i, int len) {
    int temp = arr[i];
    for (int j = 2 * i + 1; j < len; j = 2 * j + 1) {
        if (j + 1 < len && arr[j] > arr[j + 1]) {
            j++;
        }
        if (arr[j] < temp) {
            arr[i] = arr[j];
            i = j;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

public void buildMinHeap(int[] arr, int len) {
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
}

排序

大根堆排序

大根堆排序的过程是将待排序序列构建成大根堆，然后将根节点与序列最后一个元素交换位置，再将剩余的序列重新构建成大根堆，重复此过程，直到所有的元素均被排序。下面是大根堆排序的代码实现：

public void heapSort(int[] arr) {
    int len = arr.length;
    buildMaxHeap(arr, len);
    for (int i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        adjustHeap(arr, 0, len);
    }
}

小根堆排序

小根堆排序的过程与大根堆排序类似，只需将建堆和调整堆的方法改为小根堆即可。下面是小根堆排序的代码实现：

public void heapSort(int[] arr) {
    int len = arr.length;
    buildMinHeap(arr, len);
    for (int i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        adjustHeap(arr, 0, len);
    }
}

堆排序的实现

代码实现

堆排序的核心是建堆和调整堆，我们可以根据这两个过程分别封装成一个方法。下面是建堆的代码实现：

private void adjustHeap(int[] arr, int i, int len) {
    int temp = arr[i];
    for (int j = 2 * i + 1; j < len; j = 2 * j + 1) {
        if (j + 1 < len && arr[j] < arr[j + 1]) {
            j++;
        }
        if (arr[j] > temp) {
            arr[i] = arr[j];
            i = j;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

public void buildMaxHeap(int[] arr, int len) {
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
}

下面是调整堆的代码实现：

public void heapSort(int[] arr) {
    int len = arr.length;
    buildMaxHeap(arr, len);
    for (int i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        adjustHeap(arr, 0, len);
    }
}

时间和空间复杂度

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。因为堆排序是一种原地排序，不需要额外的空间。

堆排序的优化

堆的复用

建堆的过程中会重新分配内存空间，效率不高。我们可以通过将待排序序列装换为堆的方式来优化。下面是将待排序序列转换成大根堆的代码实现：

private void adjustHeap(int[] arr, int i, int len) {
    int temp = arr[i];
    for (int j = 2 * i + 1; j < len; j = 2 * j + 1) {
        if (j + 1 < len && arr[j] < arr[j + 1]) {
            j++;
        }
        if (arr[j] > temp) {
            arr[i] = arr[j];
            i = j;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

private void heapify(int[] arr, int len, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int maxIndex = i;
    if (left < len && arr[left] > arr[maxIndex]) {
        maxIndex = left;
    }
    if (right < len && arr[right] > arr[maxIndex]) {
        maxIndex = right;
    }
    if (maxIndex != i) {
        swap(arr, i, maxIndex);
        heapify(arr, len, maxIndex);
    }
}

public void buildMaxHeap(int[] arr, int len) {
    for (int i = len / 2; i >= 0; i--) {
        heapify(arr, len, i);
    }
}

堆排序的优化

我们可以使用交换法和不使用交换法两种方式实现堆排序，交换法需要不断交换堆顶元素和末尾元素，并调整堆，不使用交换法只需要将堆顶元素下移到合适的位置即可。

不使用交换

下面是不使用交换的堆排序的代码实现：

private void adjustHeap(int[] arr, int i, int len) {
    int temp = arr[i];
    int child = 2 * i + 1;
    while (child < len) {
        if (child + 1 < len && arr[child + 1] > arr[child]) {
            child++;
        }
        if (arr[child] > temp) {
            arr[i] = arr[child];
            i = child;
            child = 2 * i + 1;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

public void heapSort(int[] arr) {
    int len = arr.length;
    for (int i = len / 2; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    for (int i = len - 1; i > 0; i--) {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        adjustHeap(arr, 0, i);
    }
}

时间和空间复杂度

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。因为堆排序是一种原地排序，不需要额外的空间。

扩展点

堆与堆排序的应用

优先队列的实现

优先队列是一种特殊的队列，队列中的元素拥有优先级，高优先级的元素先出队。堆可以很方便地实现优先队列。

Top K 问题的解法

Top K 问题是指在一个无序的数据集合中，找到其中最大的K个数。堆可以很方便地实现Top K 问题。

堆排序的变种

索引堆排序

索引堆排序是一种变种的堆排序。索引堆是指一个普通的堆中的元素只能是某种具体的数据类型，而在索引堆中，元素是一个索引，根据这个索引可以得到一个数据类型的元素。索引堆排序需要另外一个数组来存储数据，堆排序的过程中只需要交换索引即可。

带权堆排序

带权堆是指堆中的元素带有权值，堆中元素的排序是根据权值大小进行的。带权堆排序的排序算法与普通堆排序一致，只需修改堆的调整过程即可。

总结

优缺点总结

堆排序的优点：

• 时间复杂度为O(nlogn)，相对较快。
• 不需要额外的空间，具有原地排序的特点。

堆排序的缺点：

• 堆的复杂度较高，建立堆的时空复杂度为O(n)，相对低效。
• 堆排序是一种不稳定的排序，相等元素在排序后位置可能变化。

学习心得分享

堆排序是一种高效的排序算法，理解堆的原理是掌握堆排序的关键。本文叙述了堆的定义与性质、建堆、排序，以及堆排序的实现和优化。在实际工程中，可以利用其建立优先队列和解决一些Top K问题。

未来研究方向

堆排序可以继续优化其建堆的过程，进一步提升堆排序的效率。此外，可以对于优先队列和Top K问题进行深入研究。