堆的定义
堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象。
堆的特性：
1.它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不 是满的，那么要求左满右不满。
2.它通常用数组来实现。
具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子 结点则分别在位置4,5,6和7，以此类推。（不使用数组的第一个位置）
如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样，在不 使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就 令k等于2k或2k+1。
3.每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个 子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。
上浮和下沉算法
堆的操作会首先进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复，我们称这个过程叫做堆的有序化。
在有序化的过程中，我们会遇到两种情况。
- 当节点的优先级上升时（在堆底加入一个新的元素时），我们需要由下至上恢复堆的顺序(即上浮 swim)。
- 当节点的优先级下降（例如将根节点替换为一个较小的元素时），我们需要由上至下恢复堆的顺序(即下沉 sink)。
上浮算法swim实现
先实现堆的比较和交换方法：
public class Heap<T extends Comparable<T>> {
private T[] items;
private int N;
public Heap(int capacity) {
this.items = (T[])new Comparable[capacity+1];
this.N = 0;
}
//比较i位置元素是否比j位置元素小
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
//交换i位置元素和j位置元素
private void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
}
因为k位置的父节点的位置是k/2，所以只要循环往上比较并交换就行了
/**
* @author wen.jie
* @date 2021/8/24 9:59
* 上浮算法
*/
private void swim(int k) {
while (k > 1 && less(k/2, k)){
exch(k/2, k);
k = k/2;
}
}
下沉算法sink实现
下沉算法中：我们需要通过父节点和它的两个子节点中的较大者交换来恢复堆。所以我们同样需要循环比较并交换，代码实现如下：
/**
* @author wen.jie
* @date 2021/8/24 9:59
* 下沉算法
*/
private void sink(int k) {
while (2*k <= N){
int j = 2*k;
if(j < N && less(j, j+1)) j++;
if(!less(k, j)) break;
exch(k, j);
k = j;
}
}
堆的插入和删除最大元素实现
堆的插入
我们将新元素加到数组末尾，增加堆的大小并让新元素上浮到合适的位置：
/**
* @author wen.jie
* @date 2021/8/24 10:59
* 向堆中添加一个元素
*/
public void insert(T t) {
items[++N] = t;
swim(N);
}
删除最大元素
我们从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适位置。
代码实现如下：
/**
* @author wen.jie
* @date 2021/8/24 10:59
* 删除堆中最大的元素
*/
public T delMax() {
T t = items[1];
items[1] = null;
exch(N--, 1);
sink(1);
return t;
}
下面提供完整的堆数据结构代码：
public class Heap<T extends Comparable<T>> {
private T[] items;
private int N;
public Heap(int capacity) {
this.items = (T[])new Comparable[capacity+1];
this.N = 0;
}
//比较i位置元素是否比j位置元素小
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
//交换i位置元素和j位置元素
private void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
/**
* @author wen.jie
* @date 2021/8/24 10:59
* 向堆中添加一个元素
*/
public void insert(T t) {
items[++N] = t;
swim(N);
}
/**
* @author wen.jie
* @date 2021/8/24 9:59
* 上浮算法
*/
private void swim(int k) {
while (k > 1 && less(k/2, k)){
exch(k/2, k);
k = k/2;
}
}
/**
* @author wen.jie
* @date 2021/8/24 9:59
* 下沉算法
*/
private void sink(int k) {
while (2*k <= N){
int j = 2*k;
if(j < N && less(j, j+1)) j++;
if(!less(k, j)) break;
exch(k, j);
k = j;
}
}
/**
* @author wen.jie
* @date 2021/8/24 10:59
* 删除堆中最大的元素
*/
public T delMax() {
T t = items[1];
items[1] = null;
exch(N--, 1);
sink(1);
return t;
}
}
堆排序
基于堆，我们可以实现一种经典而优雅的排序算法---堆排序。
堆排序实现原理:
1.构造堆；
2.得到堆顶元素，这个值就是最大值；
3.交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；
4.对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；
5.重复2~4这个步骤，直到堆中剩一个元素为止。
代码实现：
/**
* @author wen.jie
* @date 2021/8/24 14:07
*/
public class HeapSort {
public static void sort(Comparable[] pq) {
int n = pq.length;
// 构造堆
for (int k = n/2; k >= 1; k--)
//从长度一半处开始(跳过大小为1的堆)
sink(pq, k, n);
// 排序
int k = n;
while (k > 1) {
//交换第一个最大的元素和第k个元素
exch(pq, 1, k--);
//下沉重排堆,就可以得到第1个到第k-1个最大的元素
sink(pq, 1, k);
}
}
private static void sink(Comparable[] pq, int k, int n) {
while (2*k <= n) {
int j = 2*k;
if (j < n && less(pq, j, j+1)) j++;
if (!less(pq, k, j)) break;
exch(pq, k, j);
k = j;
}
}
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i-1].compareTo(pq[j-1]) < 0;
}
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i-1];
pq[i-1] = pq[j-1];
pq[j-1] = swap;
}
}
测试：
@Test
public void test(){
String[] arr = new String[]{"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
HeapSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
