堆
1.1 堆的定义
堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象。
堆的特性：
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. 每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。
堆的API设计
package Heap;
/**
* 用数组实现的Heap
* 大的放顶部
*
* @param <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;
}
}
上浮swim
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
public void swim(int k) {
//通过循环，不断比较当前节点和其父节点的值，如果父节点比当前节点小，则交换位置dan
//当k=1已经没有父节点了
while (k > 1) {
//比较父节点和当前节点
if (less(k / 2, k)) {
exch(k / 2, k);
}
k = k / 2;
}
}
下沉sink
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
int biggeer;
//通过循环，不断比较当前节点和其子节点2k和2k+1中的较大值，如果子节点比当前节点大，则交换位置
while (2 * k <= N) {
//获取当前节点的较大子节点
//如果有右节点且右边的较大
if ((2 * k + 1 <= N) && less(2 * k, 2 * k + 1)) {
biggeer = 2 * k + 1;
} else {
biggeer = 2 * k;
}
//比较当前节点和较大子节点的值
//如果当前节点小
if (less(k, biggeer)) {
//交换
exch(k, biggeer);
}
k = biggeer;
}
}
堆的实现
1.堆的插入方法insert
堆是用数组完成数据元素的存储的，由于数组的底层是一串连续的内存地址，所以我们要往堆中插入数据，我们只能往数组中从索引0处开始，依次往后存放数据，但是堆中对元素的顺序是有要求的，每一个结点的数据要大于等于它的两个子结点的数据，所以每次插入一个元素，都会使得堆中的数据顺序变乱，这个时候我们就需要通过一些方法让刚才插入的这个数据放入到合适的位置。
所以，如果往堆中新插入元素，我们只需要不断的比较新结点a[k]和它的父结点a[k/2]的大小，然后根据结果完成数据元素的交换，就可以完成堆的有序调整。
//往堆中插入一个元素
//0索引不存数据
public void insert(T t) {
items[++N] = t;
swim(N);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
public void swim(int k) {
//通过循环，不断比较当前节点和其父节点的值，如果父节点比当前节点小，则交换位置dan
//当k=1已经没有父节点了
while (k > 1) {
//比较父节点和当前节点
if (less(k / 2, k)) {
exch(k / 2, k);
}
k = k / 2;
}
}
2.delMax删除最大元素方法的实现
由大根堆的特性我们可以知道，索引1处的元素(索引0处不存数据)，也就是根结点就是最大的元素，当我们把根结点的元素删除后，需要有一个新的根结点出现，这时我们可以暂时把堆中最后一个元素放到索引1处，充当根结点，但是它有可能不满足堆的有序性需求，这个时候我们就需要通过一些方法，让这个新的根结点放入到合适的位置。
然后G再下沉到合适的位置
//删除堆中的最大元素，并返回这个最大元素
public T delMax() {
T max = items[1];
//交换索引1出的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根节点
exch(1, N);
//最大索引处的元素删除掉
items[N] = null;
//元素个数--
N--;
//让临时根节点下沉
sink(1);
return max;
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
int biggeer;
//通过循环，不断比较当前节点和其子节点2k和2k+1中的较大值，如果子节点比当前节点大，则交换位置
while (2 * k <= N) {
//获取当前节点的较大子节点
//如果有右节点且右边的较大
if ((2 * k + 1 <= N) && less(2 * k, 2 * k + 1)) {
biggeer = 2 * k + 1;
} else {
biggeer = 2 * k;
}
//比较当前节点和较大子节点的值
//如果当前节点小
if (less(k, biggeer)) {
//交换
exch(k, biggeer);
}
k = biggeer;
}
}
3.堆的代码
package Heap;
/**
* 用数组实现的Heap
* 大的放顶部
*
* @param <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;
}
//往堆中插入一个元素
//0索引不存数据
public void insert(T t) {
items[++N] = t;
swim(N);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
public void swim(int k) {
//通过循环，不断比较当前节点和其父节点的值，如果父节点比当前节点小，则交换位置dan
//当k=1已经没有父节点了
while (k > 1) {
//比较父节点和当前节点
if (less(k / 2, k)) {
exch(k / 2, k);
}
k = k / 2;
}
}
//删除堆中的最大元素，并返回这个最大元素
public T delMax() {
T max = items[1];
//交换索引1出的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根节点
exch(1, N);
//最大索引处的元素删除掉
items[N] = null;
//元素个数--
N--;
//让临时根节点下沉
sink(1);
return max;
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
int biggeer;
//通过循环，不断比较当前节点和其子节点2k和2k+1中的较大值，如果子节点比当前节点大，则交换位置
while (2 * k <= N) {
//获取当前节点的较大子节点
//如果有右节点且右边的较大
if ((2 * k + 1 <= N) && less(2 * k, 2 * k + 1)) {
biggeer = 2 * k + 1;
} else {
biggeer = 2 * k;
}
//比较当前节点和较大子节点的值
//如果当前节点小
if (less(k, biggeer)) {
//交换
exch(k, biggeer);
}
k = biggeer;
}
}
}
堆排序
堆构造（数组转成堆）
给定一个数组：
String[] arr = {“S”,“O”,“R”,“T”,“E”,“X”,“A”,“M”,“P”,“L”,“E”}
堆的构造，最直观的想法就是另外再创建一个和新数组数组，然后从左往右遍历原数组，每得到一个元素后，添加到新数组中，并通过上浮，对堆进行调整，最后新的数组就是一个堆。
上述的方式虽然很直观，也很简单，但是我们可以用更聪明一点的办法完成它。创建一个新数组，把原数组0~length-1的数据拷贝到新数组的 1~length处，再从新数组长度的一半处开始往1索引处扫描(从右往左)，然后对扫描到的每一个元素做下沉调整即可。
在构建好堆后，就符合了大根堆的父节点比子节点大的特性
堆排序
对构造好的堆，我们只需要做类似于堆的删除操作，就可以完成排序。
1.将堆顶元素和堆中最后一个元素交换位置；
2.通过对堆顶元素下沉调整堆，把最大的元素放到堆顶(此时最后一个元素不参与堆的调整，因为最大的数据已经到了数组的最右边)
3.重复1~2步骤，直到堆中剩最后一个元素。
package Heap;
public class HeapSort {
//判断heap对中索引i和j处的元素大小
private static boolean less(Comparable[] heap, int i, int j) {
return heap[i].compareTo(heap[j])<0;
}
//交换heap堆中i索引和j索引处的值
private static void exch(Comparable[] heap, int i, int j) {
Comparable tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
//根据数组构建堆
private static void createHeap(Comparable[] source , Comparable[] heap){
//把数组中的元素拷贝到堆中，形成无序堆
System.arraycopy(source,0,heap,1,source.length);
//对堆中的非叶子元素进行下沉
for (int i = (heap.length)/2;i>0;i--){
sink(heap,i, heap.length-1);
}
}
//对数组从小到大排序
private static void sort(Comparable[] source) {
//构建堆
Comparable[] heap = new Comparable[source.length + 1];
createHeap(source,heap);
//定义一个变量，记录未排序的元素中最大的索引
int N = heap.length-1;
//通过循环，交换1索引处的元素和未排序的元素中的最大索引处的元素
while(N!=1){
//交换元素
exch(heap,1,N);
//排除交换后最大元素所在的索引，让它不参与堆的下沉调整
N--;
//需要对索引1处的元素进行堆的下沉调整
sink(heap,1,N);
}
//把heap中数据复制到source中
System.arraycopy(heap,1,source,0,source.length);
}
//在heap堆中，对target处的元素做下沉，范围是0-range
private static void sink(Comparable[] heap, int target, int range) {
int biggeer;
//通过循环，不断比较当前节点和其子节点2target和2target+1中的较大值，如果子节点比当前节点大，则交换位置
while (2 *target <= range) {
//获取当前节点的较大子节点
//如果有右节点且右边的较大
if ((2 *target + 1 <= range) && less(heap,2 *target, 2 *target + 1)) {
biggeer = 2 *target + 1;
} else {
biggeer = 2 *target;
}
//比较当前节点和较大子节点的值
//如果当前节点小
if (less(heap,target, biggeer)) {
//交换
exch(heap,target, biggeer);
}
target = biggeer;
}
}
}