堆
1.堆是一种常见的数据结构，通常用于实现优先队列等应用。它是一个特殊的树形结构，具有以下特点：
- 完全二叉树结构： 堆通常是一棵完全二叉树，即除了最后一层，其他层都被填满，而且最后一层从左到右填充。
- 堆序性质： 堆分为最大堆和最小堆。在最大堆中，父节点的值始终大于或等于其子节点的值；而在最小堆中，父节点的值始终小于或等于其子节点的值。
- 数组表示： 堆可以通过数组来表示，通过数组下标之间的关系实现堆的父子关系。对于数组中的第 i 个元素，其左子节点索引为 2i 1，右子节点索引为 2i 2，父节点索引为 floor((i-1)/2)。
- 堆的操作： 堆主要支持两种基本操作：插入（Insert）和删除（Delete）。插入操作将新元素添加到堆中，而删除操作通常删除堆中的最大或最小元素，然后重新调整堆以保持堆的性质。
- 堆的应用： 堆广泛应用于各种算法和数据结构中。优先队列就是堆的一种应用，它能够以 O(log n) 的时间复杂度实现插入和删除最大或最小元素的操作。
- 堆排序： 堆排序是一种使用堆的排序算法。它首先将待排序的元素构建成一个最大堆或最小堆，然后每次将堆顶元素与堆的最后一个元素交换，然后缩小堆的范围，再次保持堆的性质，直至排序完成。
总的来说，堆是一种高效的数据结构，它在实现优先队列、堆排序等场景中发挥着重要作用。
2.在堆的进一步探讨中，我们可以深入了解堆的两个主要类型：最大堆和最小堆。
最大堆（Max Heap）：
最大堆的定义是：对于堆中的任意节点 i，其值不小于其子节点的值。这意味着根节点是堆中的最大元素。
最大堆的一些基本操作包括：
- 插入操作： 将新元素插入堆的末尾，然后通过向上调整（percolate-up）的方式，使得堆的性质得以保持。
- 删除最大元素： 移除根节点元素，将堆的最后一个元素放到根的位置，然后通过向下调整（percolate-down）的方式，保持堆的性质。
最小堆（Min Heap）：
最小堆的定义是：对于堆中的任意节点 i，其值不大于其子节点的值。这意味着根节点是堆中的最小元素。
最小堆的基本操作与最大堆类似，只是在插入和删除操作中的调整方式相反。
3.堆的时间复杂度分析：
- 插入操作： 在最坏情况下，插入元素需要进行 O(log n) 次调整，其中 n 是堆中元素的数量。
- 删除操作： 删除最大或最小元素同样需要 O(log n) 次调整。
- 建堆操作： 将一个无序数组构建成堆的时间复杂度为 O(n)。
- 堆排序： 堆排序的时间复杂度为 O(n log n)，其中 n 是待排序数组的长度。
4.堆的应用场景：
- 优先队列： 堆能够快速找到最大或最小元素，因此被广泛应用于实现优先队列。
- 图算法： 在一些图算法中，堆可以用于实现 Dijkstra 等最短路径算法。
- 操作系统调度： 堆的数据结构也在操作系统调度等领域得到应用。
总体而言，堆是一种强大而灵活的数据结构，其在算法和软件工程中的应用广泛而深刻。通过充分理解堆的性质和操作，我们能够更好地解决各种问题，并设计出高效的算法。
5.堆排序
堆排序是一种基于堆的排序算法，它利用了堆的特性来实现排序。该算法分为两个主要步骤：建堆和排序。
1. 建堆（Heapify）：
在建堆阶段，我们将无序数组构建成一个二叉堆。通常采用自底向上的方式，从最后一个非叶子节点开始，逐步向上调整，保持堆的性质。
让我们考虑一个简单的例子，假设我们有以下无序数组：
[ 4, 10, 3, 5, 1 ]
首先，将这个数组构建成一个最大堆。
- 从最后一个非叶子节点开始：
- 最后一个非叶子节点是索引 ( n/2 - 1 )。在这个例子中，( 5/2 - 1 = 1 )。
- 检查节点 ( 1 ) 和其子节点 ( 3 )、( 4 ) 的大小关系，如果有需要，交换它们。
[ 4, 10, 3, 5, 1]
- 继续向前：
- 对节点 ( 0 ) 进行同样的比较和交换操作。
[ 10,5, 3, 4, 1 ]
此时，我们已经完成了建堆的阶段，得到了一个最大堆。
2. 排序：
在排序阶段，我们不断将堆的根节点与堆的最后一个元素交换，然后减小堆的大小，并通过向下调整（percolate-down）来保持堆的性质。
- 第一次交换：
- 将堆的根节点 (10) 与最后一个元素 (1) 交换。
[ 1, 5, 3, 4, 10 ]
- 向下调整：
- 对新的根节点 (1) 进行向下调整，使得堆重新保持最大堆的性质。
[ 5, 4, 3, 1, 10 ]
- 第二次交换：
- 将堆的根节点 (5) 与倒数第二个元素 (4) 交换。
[ 4,5, 3, 1, 10]
- 向下调整：
- 对新的根节点 (4) 进行向下调整。
[ 4, 1, 3, 5, 10 ]
- 继续交换和调整：
- 重复以上步骤，直到堆的大小为 (1)，整个数组就排好序了。
最终，通过不断交换和调整，我们得到了有序的数组：
[ 1, 3, 4, 5, 10 ]
堆排序的时间复杂度为 (O(n log n))，其中 (n) 是数组的长度。虽然堆排序的常数因子较大，但它在实践中仍然是一个有效且稳定的排序算法。
4 10 10 10 3 ——》 4 3 ——》 5 3
5 1 5 1 4 1
代码语言：javascript复制//[ 4, 10, 3, 5, 1 ] n=5 i=1
public class HeapSort {
public void heapify(int arr[], int n, int i) {
int largest = i;
int leftChild = 2 * i 1;
int rightChild = 2 * i 2;
if (leftChild < n && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
if (rightChild < n && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
//[ 10,5, 3, 4, 1 ]
public void heapSort(int arr[]) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Heap sort
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr,i,0);
}
}
1,5,3,4,10 - 5,1,3,4,10 - 4,1,3,5,10 - 3,4,1,5,10 - 4,3,1,5,10 - 1,3,4,5,10
public static void main(String args[]){
int unsortedArray[] = {4,10,3,5,1};
HeapSort heapSort = new HeapSort();
heapSort.heapSort(unsortedArray);
System.out.print("Sorted array: ");
for(int i=0;i< unsortedArray.length; i){
System.out.println(unsortedArray[i] " ");
}
}
