前言

本文为本小白🤯学习数据结构的笔记，将以算法题为导向，向大家更清晰的介绍数据结构相关知识（算法题都出自🙌B站马士兵教育——左老师的课程，讲的很好，对于想入门刷题的人很有帮助👍）

上面写完了归并排序，快速排序，排序它本身整个算法并没有什么，重要的是他的算法，它怎么提升时间复杂度，以及这种思想的应用，这是我们更要去关注的。下面来看一个新的排序——堆排序。

下面来介绍一下数据结构中的“堆”（Heap）。

1.堆 (Heap) 概述

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

• 堆是一棵完全二叉树。这意味着除了最后一层，其他层都被完全填满，且最后一层的节点都尽可能地靠左排列。

• 堆的数组表示：由于堆是完全二叉树，可以用数组 heap[0…n-1] 来存储（通常索引从 0 开始）：

  • 根节点：heap[0]
  • 节点 i 的左子节点：heap[2*i + 1]
  • 节点 i 的右子节点：heap[2*i + 2]
  • 节点 i 的父节点：heap[(i-1) / 2] (整数除法)

这种表示法非常节省空间，且父子节点的访问是 O(1) 的。

        索引: 0 (值: 50)
       /                  \
  索引: 1 (值: 30)     索引: 2 (值: 40)
   /        \           /        \
索引:3    索引:4     索引:5     索引:6
(值:20)   (值:10)   (值:35)   (值:25)

数组索引:   0     1     2     3     4     5     6
         +-----+-----+-----+-----+-----+-----+-----+
数组值:   | 50  | 30  | 40  | 20  | 10  | 35  | 25  |
         +-----+-----+-----+-----+-----+-----+-----+

2.堆主要有两种类型：

大根堆 (Max Heap)：对于树中的任意节点，其值大于或等于其子节点的值。因此，根节点（堆顶）是整个堆中最大的元素。

实现大根堆：

package DiGui;

public class Dui {

    public static void heapInsert(int [] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    
    public static void swap(int [] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

大根堆应用: 去掉堆中的最大值，其结构仍保持大根堆

实现思路：
1.找到堆中最大值：肯定是数组中，下标为0的数，这个很简单。
2.去掉最大值保持大根堆：将数组中下标最大的数，赋值给下标为0位置，在用heapify方法往下调整堆结构。

（heapify方法）：

//构建堆，index：构建堆结构下表，一下全是堆结构，heapSize：整个arr数组长度防止越界
public static void heapify(int [] arr. int index, int heapSize){
    //index 左孩子
    int left = index * 2 + 1;
    while (left < heapSize) {
        //index右孩子，与左孩子比较，取最大值下标
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        //判断arr[largest] 与 arr[index] 大小取最大值下标
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap( arr, largest, index);
        index = largest;
     }
}

public static void swap(int [] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
    

时间复杂度O(logN)

最小堆 (Min Heap)：对于树中的任意节点，其值小于或等于其子节点的值。因此，根节点（堆顶）是整个堆中最小的元素。

堆排序

先来看代码吧：

package DiGui;

public class Dui {
    public static void heapSort(int [] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //先把整个数组变成大根堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
       
        int heapSize = arr.length;
        //不断把堆顶的最大值“拿下来”，放到数组末尾
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            //每次拿走最大值后，重新调整堆，使其继续保持大根堆的性质
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

   
    public static void heapInsert(int [] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int [] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
        }
    }

    public static void swap(int [] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

其实就是把上面两个问题结合起来

来看看整体思想：

🌟 堆排序的核心思想

目标： 把一个无序数组变成升序有序的数组。

方法：

• 先将整个数组构造成一个 大根堆（最大值在堆顶）。
• 然后不断把堆顶的最大值“拿下来”，放到数组末尾，同时缩小堆的范围。
• 每次拿走最大值后，重新调整堆，使其继续保持大根堆的性质。（heaify方法）
• 重复这个过程，直到所有元素都被放到正确位置。
• 最终结果就是：从小到大排序完成。

时间复杂度：O（N*logN）空间：O(1)

堆排序扩展题目：
已知一个几乎有序的数组，几乎有序是指，如果把数组排好序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

public void sortedArrDistanceLessK (int [] arr, int k) {
        PriorityQueue <Integer> heap = new PriorityQueue<>();

        int index = 0;
        for ( ; index < Math.min(arr.length, k); index++) {
            heap.add(arr[index]);
        }

        int i = 0;
        for (; index < arr.length; i++, index++) {
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }
        
        while(!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
        
    }

小白啊！！！写的不好轻喷啊🤯如果觉得写的不好，点个赞吧🤪（批评是我写作的动力）

…。。。。。。。。。。。…

…。。。。。。。。。。。…