常用数据结构与算法实现
以下博客根据B站罗召勇老师视频：数据结构与算法基础-Java版（罗召勇）写的详细笔记
数据结构与算法基础：
数据结构与算法之基础概述
数据结构：
（一）数据结构与算法之数组
（二）数组结构与算法之栈
（三）数据结构与算法之队列
（四）数据结构与算法之链表
（五）数据结构与算法之树结构基础
（六）数据结构与算法之二叉树大全
（七）数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)
（八）数据结构与算法之多路查找树（2-3树、2-3-4树、B树、B+树）
（九）数据结构与算法之图结构
十大经典算法：
（一）数据结构与算法之冒泡排序（含改进版）
（二）数据结构与算法之选择排序（含改进版）
（三）数据结构与算法之插入排序（含改进版）
（四）数据结构与算法之希尔排序
（五）数据结构与算法之归并排序
（六）数据结构与算法之快速排序
（七）数据结构与算法之堆排序
（八）数据结构与算法之计数排序
（九）数据结构与算法之桶排序
（十）数据结构与算法之基数排序
堆排序概述
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)
1）假设给定无序序列结构如下
2）此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整
3）找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换
4）这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
此时，我们就将一个无需序列构造成了一个大顶堆
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换
1）将堆顶元素9和末尾元素4进行交换，9就不用继续排序了
2）重新调整结构，使其继续构建大顶堆（9除外）
3）再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
步骤三 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
排序思路：
将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
动图展示：
代码实现
import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = {4, 6, 8, 5, 9}; heapSort(arr); // [4, 6, 8, 5, 9] // [4, 9, 8, 5, 6] // [4, 9, 8, 5, 6] // [9, 6, 8, 5, 4] // [9, 6, 8, 5, 4] // [9, 6, 8, 5, 4] // [8, 6, 4, 5, 9] // [8, 6, 4, 5, 9] // [6, 5, 4, 8, 9] // [6, 5, 4, 8, 9] // [5, 4, 6, 8, 9] // [5, 4, 6, 8, 9] // [4, 5, 6, 8, 9] } //堆排序 public static void heapSort(int[] arr) { //开始位置是最后一个非叶子节点（最后一个节点的父节点） int start = (arr.length - 1) / 2; //循环调整为大顶堆 for (int i = start; i >= 0; i--) { maxHeap(arr, arr.length, i); } //先把数组中第0个和堆中最后一个交换位置 for (int i = arr.length - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; //再把前面的处理为大顶堆 maxHeap(arr, i, 0); } } //数组转大顶堆,size:调整多少（从最后一个向前减），index:调整哪一个（最后一个非叶子节点） public static void maxHeap(int[] arr, int size, int index) { //左子节点 int leftNode = 2 * index + 1; //右子节点 int rightNode = 2 * index + 2; //先设当前为最大节点 int max = index; //和两个子节点分别对比，找出最大的节点 if (leftNode < size && arr[leftNode] > arr[max]) { max = leftNode; } if (rightNode < size && arr[rightNode] > arr[max]) { max = rightNode; } //交换位置 if (max != index) { int temp = arr[index]; arr[index] = arr[max]; arr[max] = temp; //交换位置后，可能会破坏之前排好的堆，所以之间排好的堆需要重新调整 maxHeap(arr, size, max); } //打印每次排序后的结果 System.out.println(Arrays.toString(arr)); } }
时间复杂度
最优时间复杂度：o(nlogn)
最坏时间复杂度：o(nlogn)
稳定性：不稳定
它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为log2i＋1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。
所以总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。
空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录的比较与交换是跳跃式进行，因此堆排序是一种不稳定的排序方法。
