一.堆的介绍
动态效果图
堆有如下特点的二叉树：
1.他是完全的二叉树。也就是说，，除了树的最后一层布需要时满的，其他的每一层从左到右都是满的.(如下图的完全二叉树跟不完全二叉树)
2.它常常用一个数组在实现。（如下图显示了堆它与数组之间的关系。堆在存储器中的表示是数组；堆只是概念上的表示。注意树是完全二叉树，并且所有的节点满足堆的条件）
3.堆中的每一个节点都满足堆的条件，也就是说每一个节点的值都大于或者等于这个节点的子节点的值（如上图）
二，堆的移除
1.只能移除根
2.把最后一个节点移动到根的位置
3.一直向下筛选这个节点，直到它在一个大于它的节点之下，小于它的节点之上
如下图：
不过要注意向下筛选选择较大子节点交换位置如下图
三.堆的插入
1节点初始化插入数组最后一个空的位置，使用向上筛选（目标节点只用跟它的父节点比较）
如下图
四.不是真的交换
不管是堆插入节点还是删除节点都不真的交换，如下图：在三次交换后A在D的位置上，B,C,D向上移动一位，a图中异常交换使用3次复杂，3次交换就是9次复杂。而b图中总共才使用5次复制。所以很明显我们使用b图的方式
四.堆节点的特征
若数组的某节点索引值为x那么：
1.它的父节点的下标为(x-1)/2
2.它的左子节点下标为2*x+1
3.它的右子节点下标为2*x+2
五.堆排序算法
堆的数据结构引出了很有效率的排序算法，称为堆排序算法
排序过程中使用同一数组如下图
六，堆排序的java代码package data;import java.util.Arrays;import java.util.Random;/** * 堆排序 * @author JYC506 * */public class HeapSort {public static void sort(int[] arr){Heap heap=new Heap(arr.length);for(int i=0;i<arr.length;i++){heap.insert(arr[i]);}for(int i=arr.length-1;i>-1;i–){arr[i]=heap.remove();}}public static void main(String[] args) {/*创建堆*/int num=10;Heap heap=new Heap(num);int[] arr=new int[num];Random ran=new Random();for(int i=0;i<num;i++){int data= ran.nextInt(num);heap.insert(data);arr[i]=data;}System.out.println(heap);for(int i=0;i<num;i++){System.out.println("移除出来的数据:"+heap.remove());}System.out.println("移除完所有数据后的堆里面的数组的情况:"+heap);/*直接用堆排序*/System.out.println("堆排序前："+Arrays.toString(arr));HeapSort.sort(arr);System.out.println("堆排序后："+Arrays.toString(arr));}}/** * 堆 * */class Heap {/*当前存储空间*/private int[] arr;/*最大的范围*/private int maxSize;/*现在的大小*/private int currentSize;public Heap(int maxSize) {this.maxSize = maxSize;this.currentSize = 0;this.arr = new int[maxSize];}public int remove() {int data = arr[0];/*移除根并且把最后一个节点移动到跟的位置，大小减一*/this.arr[0] = arr[–currentSize];/*渗透*/this.trickleDown(0);/*删除的部分使用同一数组*/arr[this.currentSize]=data;return data;}public boolean insert(int data) {if (currentSize == maxSize) {return false;}arr[currentSize] = data;/*冒泡*/this.trickleUp(currentSize++);return true;}/*插入数据时冒泡*/private void trickleUp(int index) {int parent = (index – 1) / 2;int buttom = arr[index];/*当有父节点时*/while (index > 0 && arr[parent] < buttom) {arr[index] = arr[parent];index=parent;parent = (parent – 1) / 2;}arr[index] = buttom;}/*删除数据时候渗透*/private void trickleDown(int index) {int largerChild;int top = arr[index];/*当有子节点*/while (index < this.currentSize / 2) {int leftChild = 2 * index + 1;int rightChild = leftChild + 1;if (rightChild < currentSize && arr[leftChild] < arr[rightChild]) {largerChild = rightChild;} else {largerChild = leftChild;}if (top > arr[largerChild]) {break;}arr[index] = arr[largerChild];index = largerChild;}arr[index] = top;}@Overridepublic String toString() {return "Heap [arr=" + Arrays.toString(arr) + "]";}public int[] getArr() {return arr;}}运行结果如下
生活是一段奇妙的旅行，就在那一去无返的火车上。
