概述
堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象。
堆的特性：
-
它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。
-
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中：
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
-
大顶堆：
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] -
小顶堆：
arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆的实现
实现方式
堆的形式是一棵树，但是我们可以用数组来实现它，父节点和孩子节点的父子关系通过数组下标来确定。
在实现堆的过程中，采用第二种方式，即结点编号从1开始。
API设计
类名：Heap
构造方法：Heap(int capacity)：创建容量为capacity的Heap对象
成员方法
private boolean less(int i,int j)：判断堆中索引i处的元素是否小于j处的元素
private void exch(int i,int j)：交换堆中i索引和j索引处的值
public T delMax()：删除堆中最大的元素,并返回这个最大元素
public void insert(T t)：往堆中插入一个元素
private void swim(int k)：使用上浮算法，使索引k的元素在堆中处于正确的位置
private void sink(int k)：使用下沉算法，使索引k处元素在堆中处于正确的位置
成员变量
private T[] imtes：用来存储元素的数组
private int n：记录堆中元素的个数
代码实现
insert()方法
堆是用数组完成数据元素的存储的，由于数组的底层是一串连续的内存地址，所以我们要往堆中插入数据，我们只能往数组中从索引0处开始，依次往后存放数据，但是堆中对元素的顺序是有要求的，每一个结点的数据要大于等于它的两个子结点的数据，所以每次插入一个元素，都会使得堆中的数据顺序变乱，这个时候我们就需要通过一些方法让刚才插入的这个数据放入到合适的位置。
所以，如果往堆中新插入元素，我们只需要不断的比较新结点a[k]和它的父结点a[k/2]的大小，然后根据结果完成数据元素的交换，就可以完成堆的有序调整。
delMax()删除最大元素
由堆的特性我们可以知道，索引1处的元素，也就是根结点就是最大的元素，当我们把根结点的元素删除后，需要有一个新的根结点出现，这时我们可以暂时把堆中最后一个元素放到索引1处，充当根结点，但是它有可能不满足堆的有序性需求，这个时候我们就需要通过一些方法，让这个新的根结点放入到合适的位置。
所以，当删除掉最大元素后，只需要将最后一个元素放到索引1处，并不断的拿着当前结点a[k]与它的子结点a[2k] 和a[2k+1]中的较大者交换位置，即可完成堆的有序调整。
public class Heap {
//存储元素
private Integer[] items;
//记录堆中的元素个数
private int n;
public Heap(int capacity) {
items = new Integer[capacity + 1];
n = 0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i, int j) {
return items[i] < items[j];
}
//交换堆中索引i处和索引j处的值
private void exch(int i, int j) {
int temp = items[i];
items[i] = items[j];
items[j] = temp;
}
//判断堆中最大的元素，并返回这个最大元素
public Integer delMax() {
// 获取最大值
Integer max = items[1];
// 交换索引1 处和索引n处的值
exch(1, n);
// 删除索引n处的值
items[n] = null;
// 个数-1
n--;
// 下沉
sink(1);
return max;
}
public int size() {
return n;
}
//往堆中插入一个元素
public void insert(Integer item) {
items[++n] = item;
// 上浮
swim(n);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
// 判断k是否大于1，大于1的情况下再上浮
while (k > 1) {
// 比较当前节点和父节点，如果父节点比当前结点小，那么就交换
if (less(k / 2, k)) {
exch(k / 2, k);
}
k = k / 2;
}
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
// 判断当前是不是数组末尾
while (k * 2 <= n) {
// 找到子节点中的较大者
int maxIndex;
if (k * 2 + 1 <= n) {
// 存在右子结点
if (less(k * 2, k * 2 + 1)) {
// 左节点比右节点小
maxIndex = k * 2 + 1;
} else {
maxIndex = k * 2;
}
} else {
// 不存在右结点
maxIndex = k * 2;
}
// 比较当前节点和子节点中的较大者，如果当前结点不小，就结束循环
if (!less(k, maxIndex)) {
break;
}
// 当前节点小，交换位置
exch(k, maxIndex);
k = maxIndex;
}
}
}
堆排序
步骤：
-
构造堆；
-
得到堆顶元素，这个值就是最大值；
-
交换堆顶元素和数组中的最后一个元素，此时所有元素中最大元素已经放到合适的位置；
-
对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；
-
重复2~4这个步骤，直到堆中剩一个元素为止。
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
public void sink(int k, int end) {
// 判断当前是不是数组末尾
while (k * 2 <= end) {
// 找到子节点中的较大者
int maxIndex;
if (k * 2 + 1 <= end) {
// 存在右子结点
if (less(k * 2, k * 2 + 1)) {
// 左节点比右节点小
maxIndex = k * 2 + 1;
} else {
maxIndex = k * 2;
}
} else {
// 不存在右结点
maxIndex = k * 2;
}
// 比较当前节点和子节点中的较大者，如果当前结点不小，就结束循环
if (!less(k, maxIndex)) {
break;
}
// 当前节点小，交换位置
exch(k, maxIndex);
k = maxIndex;
}
}
//根据数组构造堆
public void initHeap(Integer[] arr) {
// 遍历数组，将数组中的元素添加到堆中
for (int i = 0; i < arr.length; i++) {
items[i + 1] = arr[i];
n++;
}
// 从items的n/2位置遍历到1位置
for (int i = n / 2; i > 0; i--) {
sink(i, n);
}
}
public Integer get(int i) {
return items[i];
}
//堆排序
public static void sort(Integer[] arr) {
// 构造堆
// 创建一个比原数组大1的堆
Heap heap = new Heap(arr.length);
heap.initHeap(arr);
// 构造堆
int index = heap.size();
while (index != 1) {
heap.exch(1, index);
index--;
// 交换完了，下沉
heap.sink(1, index);
}
// 堆中的数据已经有序，拷贝到arr中
for (int i = 0; i < arr.length; i++) {
arr[i] = heap.get(i + 1);
}
}
public static void main(String[] args) {
Integer[] arr = {3, 6, 1, 2, 9, 7, 8, 4, 5, 10, 11};
sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
评论区