摘要：堆排序的时间复杂度非常的稳定，是，并且是原地排序算法，具体是怎么实现的呢我们一般把堆排序分为两个步骤建堆和排序。
1. 什么是堆
堆（Heap），其实是一种特殊的二叉树，主要满足了二叉树的两个条件：
堆是一种完全二叉树，还记得完全二叉树的定义吗？叶节点都在最底下两层，最后一层的节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种树叫做完全二叉树。
堆中的每个节点的值都必须大于等于（或者小于等于）其左右子节点的值。
对于堆中的每个节点都大于等于其左右子节点的值，叫做大顶堆，反之，则叫做小顶堆。看看下面的图就能懂了。
其中，1 是大顶堆，2 是小顶堆，3 不是堆。
2. 堆是如何存储的？
其实，堆可以按照完全二叉树的存储方式来储存，因为完全二叉树是比较省空间的，所以我们可以直接用数组来存储，然后按照数组下标来取出堆中数据。参照下图，来看看堆的存储：
其中，对于任意位置上的节点 i ，其左子节点是 2 * i + 1，右子节点是 2 * i + 2，父节点是 (i - 1) / 2。
3. 堆的几种操作
明白了堆是怎样储存的，我们在来看看堆最常见的两个操作：往堆中插入元素和删除堆顶元素。
首先，如果要往堆中插入一个元素，我们先将其插入到数组中最后一个位置，然后与其父节点的值进行比较，如果大于父节点，则交换位置，继续比较。看看下面的图你就明白了：
交换操作的代码，我也放到这里：
public class Heap {
private int[] data;//存储堆数据的数组
private int n;//堆中可存储的元素容量
private int size;//堆中存储的元素个数
public Heap(int capacity) {
this.data = new int[capacity];
this.n = capacity;
this.size = 0;
}
//往堆中插入数据
public void insert(int value){
if (size >= n) return;//堆满了
data[size] = value;
int i = size;
while ((i - 1) / 2 >= 0 && data[i] > data[(i - 1) / 2]){
//交换data[i] 极其父节点 data[(i - 1) / 2] 的值
swap(data, i, (i - 1) / 2);
i = (i - 1) / 2;
}
size ++;
}
//交换数组两个位置的元素
private void swap(int[] data, int i, int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
接下来看看第二种操作：删除堆顶元素。
根据堆的定义，堆顶元素其实就是堆的最大或最小元素。所以删除堆顶元素，我们只需要移除数组中的第 0 个元素，然后再进行堆化，让堆继续保持顺序。那该怎么进行堆化呢？
首先我们直接将堆中的最后一个元素移到堆顶，然后与其左右子节点的值进行比较，找到较大的那么子节点，交换位置，然后继续比较，你可以结合代码来理解一下：
//删除数据，如果是大顶堆，则删除的是堆中的最大元素
//如果是小顶堆，则删除的堆中的最小元素
public int removeMax(){
if (size == 0) return -1;//堆为空
//将数组中的最后一个元素，放到第一个位置
int result = data[0];
data[0] = data[size - 1];
data[-- this.size] = 0;
//进行堆化
heapify(data, size, 0);
return result;
}
//堆化函数
private void heapify(int[] data, int size, int i){
while (true){
int max = i;
if ((2 * i + 1) < size && data[i] < data[2 * i + 1]) max = 2 * i + 1;
if ((2 * i + 2) < size && data[max] < data[2 * i + 2]) max = 2 * i + 2;
if (max == i) break;
swap(data, i, max);
i = max;
}
}
4. 堆排序
现在来看看里用堆这种数据结构是怎么实现排序功能的。堆排序的时间复杂度非常的稳定，是O(nlogn)，并且是原地排序算法，具体是怎么实现的呢？我们一般把堆排序分为两个步骤：建堆和排序。
建堆
对于一个未排序的数组，例如 data[3,5,8,2,1,4,6]，其原始的结构是这样的：
可以看到第一个非叶子节点是 8，所以我们从 8 开始从上往下堆化，然后依次是 5 - 3，堆化后的效果就是这样的：
这样，我们就将一个无序的数组堆化成了具有堆的性质的数据，还需要说明以下，如果确定一个堆的第一个非叶子节点是多少呢？实际上，对于长度为 length 的数组，(length - 2) / 2下标对应的数据，就是堆中的第一个非叶子节点。接下来的操作就是排序了。
排序
排序的过程类似于上面说到的删除堆顶元素，因为堆顶元素是堆的最大或最小元素，以大顶堆为例，我们只需要将堆顶元素和数组中最后一个元素交换位置，然后重新构造堆，继续交换堆顶元素和数组中最后一个未排序数据，知道堆中元素剩下最后一个。
示意图如下：
整个建堆和排序的实现的代码也贴在这里：
//堆排序
public void heapSort(int[] data){
int length = data.length;
if (length <= 1) return;
//建堆
buildHeap(data);
while (length > 0){
swap(data, 0, --length);
heapify(data, length, 0);
}
}
//建堆
//从非叶子节点依次堆化
private void buildHeap(int[] data){
int length = data.length;
for (int i = (length - 2) / 2; i >= 0; -- i) {
heapify(data, length, i);
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/74035.html
摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法为王。 想学好前端，先练好内功，只有内功深厚者，前端之路才...
摘要：二叉堆数据结构是一种特殊的二叉树，他能高效快速的找出最大值和最小值，常应用于优先队列和著名的堆排序算法中。 二叉堆数据结构是一种特殊的二叉树，他能高效、快速的找出最大值和最小值，常应用于优先队列和著名的堆排序算法中。 二叉堆 二叉堆有以下两个特性： 是一颗完全二叉树，表示数的每一层都有左侧和右侧子节点（除最后一层的叶节点），并且最后一层的叶节点尽可能是左侧子节点 二叉堆不是最小堆就是...
摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。 前面介绍了七大算法的思想与实现步骤，下面来做一个归总。 排序方法 平均复杂度 最坏复杂度 最好复杂度 辅助空间 稳定性 直接选择排序 O(n^2...
摘要：一虚拟机内存图解程序运行与虚拟机之上，运行时需要内存空间。是一种数据结构，是虚拟机中的局部变量表，对应物理层之上的程序数据模型。 一：虚拟机内存图解 JAVA 程序运行与虚拟机之上，运行时需要内存空间。虚拟机执行 JAVA 程序的过程中会把它管理的内存划分为不同的数据区域方便管理。 虚拟机管理内存数据区域划分如下图： showImg(https://segmentfault.com/i...
摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法为王。想学好前端，先练好内功，内功不行，就...
阅读 3120·2021-11-12 10:36
阅读 1173·2019-08-30 15:56
阅读 2393·2019-08-30 11:26
阅读 467·2019-08-29 13:00
阅读 3552·2019-08-28 18:08
阅读 2713·2019-08-26 17:18
阅读 1853·2019-08-26 13:26
阅读 2388·2019-08-26 11:39
