堆也是一种二叉树数据结构，也可以说是一种完全二叉树，但不一定是一颗满二叉树。
-
满二叉树，当一个树的深度为n(n >= 1)时，该棵树共有2^n - 1个节点的树称为满二叉树
-
完全二叉树，当一个树的深度为n(n >= 1)时，需满足该课树前 n-1层为2^(n-1) - 1个节点，如果最后一层的节点数不等于2^(n-1)次方个节点，则为完全二叉树，且最后一层的节点需要从左往右排列，则称为完全二叉树。
图二为不完全二叉树，因为最后一层的叶子节点没有满足从左往右排列。
-
堆不同于树，在树结构中，父节点一般要大于左子节点，小于其右子节点，也就是说比某个节点小的，存放于该节点的左子树上，比该节点大的，存放于该节点的右子树上。而在堆数据结构中，要求父节点要大于等于两个子节点，而对两个子节点的顺序没有要求。
-
堆用数据实现示意图如下：
从第一个元素开始存储数据，第一个元素就是整个树的根节点，
2和3下标处的元素为下标1处元素的两个子节点，同理，下标4，5的两个元素为下标2元素的两个节点。得出下标k节点的两个子节点的位置为2k(左子节点)和2k+1(右子节点)。一个节点k的父节点的位置为 k/2。
- 堆数据存储
1.定义一个指针，指向数组中最后一个元素位置 + 1，将新元素插入数组，此时为了保证堆的有序性，需要使用上浮算法，将新插入的元素替换到指定位置。
- 定义一个指针，记录当前新插入元素的位置p,找到其父元素的位置p/2,比较当前元素与其父元素的大小，如果比父元素大，则交换位置。更新p的值，p = p / 2 再次找到父元素的父元素的位置，当发现p处元素小于p/2处元素或p > 1(根节点的位置为1)时就退出循环。循环完成，新插入的元素就被替换到了合适位置。
- 删除堆中最大一个元素
- 由于下标为1处元素的值是最大的，交换数组第一个元素与最后一个元素的值，让数组最后一个元素等于null。此时相当于删除了最大元素。但是最后一个元素到了第一个位置，为了保证该元素能去到合适位置，需要使用下沉算法将该元素替换到指定位置。
- 设当前元素的下标为k，找到k的两个子节点2k和2k+ 1，比较两者中较大一个，如果k比较大一个小，则交换位置，k = 2k 或 k = 2k + 1，当k比其中一个大或者2k大于数组的length时，则退出循环。此时该元素通过下沉法存入了指定位置。
public class Heap三、堆排序> { //存储堆中的元素 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; } //往堆中插入一个元素 public void insert(T t){ items[++N]=t; swim(N); } //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置 private void swim(int k){ //通过循环，不断的比较当前结点的值和其父结点的值，如果发现父结点的值比当前结点的值小，则交换位置 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; //元素个数-1 N--; //通过下沉调整堆，让堆重新有序 sink(1); return max; } //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置 private void sink(int k){ //通过循环不断的对比当前k结点和其左子结点2*k以及右子结点2k+1处中的较大值的元素大小，如果当前结点小，则需要交换位置 while(2*k<=N){ //获取当前结点的子结点中的较大结点 int max;//记录较大结点所在的索引 if (2*k+1<=N){ if (less(2*k,2*k+1)){ max=2*k+1; }else{ max=2*k; } }else { max = 2*k; } //比较当前结点和较大结点的值 if (!less(k,max)){ break; } //交换k索引处的值和max索引处的值 exch(k,max); //变换k的值 k = max; } } public static void main(String[] args) { Heap heap = new Heap (20); heap.insert("A"); heap.insert("B"); heap.insert("C"); heap.insert("D"); heap.insert("E"); heap.insert("F"); heap.insert("G"); String del; while((del=heap.delMax())!=null){ System.out.print(del+","); } } }
给定数组A；Integer[] arr = {19,22,157,465,22,95,23,44,531,107,2,11};使用堆数据结构对数组进行排序。
- 创建一个新数组B，将数组A 0-length-1处的值拷贝到数组B 1-length处，然后对B数组length / 2前的元素依次下沉，下沉完成以后，此时B数组就是一个合理的堆。
- 定义一个指针k，k为每次下沉范围，交换数组1与数组最后一个元素的位置，此时最大的元素来到了数组最后。然后将第一个元素下沉n，此时的下沉条件是2n < k,每次下沉一个元素，k–。最终是一个有序的堆。
堆排序实现
import java.util.Arrays;
public class HeapSortV2 {
public static void sortByHeap(Comparable[] source){
Comparable[] temp = new Comparable[source.length + 1];
System.arraycopy(source,0,temp,1,source.length);
//修正temp为合理的堆结构
for (int i = temp.length / 2;i >0; i--) {
sink(temp,i,temp.length - 1);
}
//开始交换数组元素
sort(temp);
//拷贝回原数组
for (int i = 0; i < source.length; i++) {
source[i] = temp[i + 1];
}
}
private static void sort(Comparable[] temp) {
int p = temp.length - 1;
while (p > 1){
exchange(temp,1,p);//交换第一个元素和最后一个元素的位置，此时最大元素来到了最后
//下沉第一个元素.此时注意，下沉的范围只要 p - 1即可
sink(temp,1,p-1);
p--;
}
}
//比较i处的值是否小于j处的值
private static boolean less(Comparable[] arr,int i,int j){
return arr[i].compareTo(arr[j]) < 0;
}
private static void exchange(Comparable[] arr,int i,int j ){
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//下沉元素
private static void sink(Comparable[] temp, int i,int range) {
while (i * 2 <= range){
//不能这样判断，造成数组下标越界异常
// if (temp[(i * 2) + 1] == null){
if ((i * 2) + 1 > range){
//没有右节点，直接比较左节点
if (less(temp,i,i * 2)){
exchange(temp,i,i * 2);
i = i * 2;
}else {
break;
}
}else {
//比较左右节点的大者
int max = 0;
if (less(temp,i * 2,(i * 2) + 1)){
max = (i * 2) + 1;
}else {
max = i * 2;
}
if (less(temp,i,max)){
//交换位置
exchange(temp,i,max);
i = max;
}else {
break;
}
}
}
}
public static void main(String[] args) {
Integer[] arr = {19,22,157,465,22,107,2,11};//[null, 465, 22, 157, 19, 22, 107, 2, 11]
//[null, 465, 22, 157, 19, 22, 107, 2, 11]
sortByHeap(arr);
System.out.println("arr " + Arrays.toString(arr));
}
}
