堆

堆

1.堆是一种常见的数据结构，通常用于实现优先队列等应用。它是一个特殊的树形结构，具有以下特点：

1. 完全二叉树结构： 堆通常是一棵完全二叉树，即除了最后一层，其他层都被填满，而且最后一层从左到右填充。
2. 堆序性质： 堆分为最大堆和最小堆。在最大堆中，父节点的值始终大于或等于其子节点的值；而在最小堆中，父节点的值始终小于或等于其子节点的值。
3. 数组表示： 堆可以通过数组来表示，通过数组下标之间的关系实现堆的父子关系。对于数组中的第 i 个元素，其左子节点索引为 2i+1，右子节点索引为 2i+2，父节点索引为 floor((i-1)/2)。
4. 堆的操作： 堆主要支持两种基本操作：插入（Insert）和删除（Delete）。插入操作将新元素添加到堆中，而删除操作通常删除堆中的最大或最小元素，然后重新调整堆以保持堆的性质。
5. 堆的应用： 堆广泛应用于各种算法和数据结构中。优先队列就是堆的一种应用，它能够以 O(log n) 的时间复杂度实现插入和删除最大或最小元素的操作。
6. 堆排序： 堆排序是一种使用堆的排序算法。它首先将待排序的元素构建成一个最大堆或最小堆，然后每次将堆顶元素与堆的最后一个元素交换，然后缩小堆的范围，再次保持堆的性质，直至排序完成。

总的来说，堆是一种高效的数据结构，它在实现优先队列、堆排序等场景中发挥着重要作用。

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 ]

首先，将这个数组构建成一个最大堆。

1. 从最后一个非叶子节点开始：
   • 最后一个非叶子节点是索引 ( n/2 - 1 )。在这个例子中，( 5/2 - 1 = 1 )。
   • 检查节点 ( 1 ) 和其子节点 ( 3 )、( 4 ) 的大小关系，如果有需要，交换它们。

   [ 4, 10, 3, 5, 1]

2. 继续向前：
   • 对节点 ( 0 ) 进行同样的比较和交换操作。

   [ 10,5, 3, 4, 1 ]

此时，我们已经完成了建堆的阶段，得到了一个最大堆。

2. 排序：

在排序阶段，我们不断将堆的根节点与堆的最后一个元素交换，然后减小堆的大小，并通过向下调整（percolate-down）来保持堆的性质。

1. 第一次交换：
   • 将堆的根节点 (10) 与最后一个元素 (1) 交换。

   [ 1, 5, 3, 4, 10 ]

2. 向下调整：
   • 对新的根节点 (1) 进行向下调整，使得堆重新保持最大堆的性质。

   [ 5, 4, 3, 1, 10 ]

3. 第二次交换：
   • 将堆的根节点 (5) 与倒数第二个元素 (4) 交换。

   [ 4,5, 3, 1, 10]

4. 向下调整：
   • 对新的根节点 (4) 进行向下调整。

   [ 4, 1, 3, 5, 10 ]

5. 继续交换和调整：
   • 重复以上步骤，直到堆的大小为 (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

//[ 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]+" ");
        }
    }