堆和堆排序
姓名：王怀帅 学号：16040410035
转载自：http://www.jianshu.com/p/86428cb6db54=有修改
【嵌牛导读】：使用普通数组或者顺序数组也可以达到优先队列的操作，但是使用堆的效率最高
【嵌牛鼻子】：优先队列、优先队列的优化、堆和堆排序
【嵌牛提问】：队列优化为什么要通过堆来实现？
【嵌牛正文】：
优先队列
优先队列是什么:
与常见的队列不同的是，优先队列并不遵循“先进先出”的原则，反而是根据优先级来确定是否先出。优先级高的先出，优先级低的后出。
为什么使用优先队列:
优先队列是用在，处理动态的数据排序。也就是优先队列所处理的数据可能时刻在变化的。
例子：医院排队，病情紧急的病人，先去治疗。该情景中：1.病人是可能时刻在增加的，也就是动态的。其次，是按优先级进行进出的
优先队列的实现
预先知识
为什么使用堆
和所有的队列一样，队列包含两种操作:1.入队，2.出队
使用普通数组或者顺序数组也可以达到优先队列的操作，但是使用堆的效率最高
也许你的表情是
大佬息怒先看这个表（优先级最高的数据进行操作的算法复杂度）
入队出队
普通数组O(1)O(n)
顺序数组O(n)O(1)
堆O(lgn)O(lgn)
从上表可以得到，用堆的算法复杂度是最低的。
在最差的情况下，使用数组是O(n^2),但是使用堆O(nlgn)
现在是不是应该
堆的基础知识
我们实现的方式是使用二叉堆（完全二叉树）
完全二叉树
特点：
每个根节点最多只有两个子节点
子节点小于根节点
除去最后一层，其他层的节点必须为最大值
最后一层可以不是最大值，但它必须在二叉树的最左边
使用数组来完成一个堆
数组堆
由图可以的到如下性质：
左子节点的索引是根节点的两倍
右子节点的索引是根节点的两倍加一
因此我们可以得到的公式：
得到当前索引i的父节点是i/2
得到当前索引的左子节点是i*2
得到当前索引的右子节点是i*2+1
得到当前堆最后一个带有子节点的父节点索引是conut/2其中conut为堆的长度
常用操作
插入一个新元素在堆的最后并排序shiftUp操作
shiftUp
如图我们在最大堆中插入一个新元素30，那么它先与其父节点（父节点位置公式在上面）进行比较，也就是图中的16,30明显大于16，进行交换位置。新元素继续和其父节点也就是41，进行比较大小。很显然，小于41，那么shiftUp操作结束
在父节点中存在一个小于子节点的数，要进行的操作shiftDown
shiftDown
如图，一共为两个步骤
左右子节点相互比较，选出最大值
与父节点进行比较，如果大于父节点进行替换
优先队列的代码实现(使用堆的方式)
满足一个数据结构
public class MaxHeap {
protected Item[] datas;
protected int count; //元素的个数
private int capacity; //预先申请空间大小
public MaxHeap(int capacity) {
this.capacity = capacity;
datas= (Item[]) new Comparable[capacity+1];//加一的原因是
count=0;
}
public int size(){
return count;
}
public boolean isEmpty(){
return count == 0;
}
}
常用操作shiftUp和shiftDown实现(具体操作描述在上面已经讲述)
private void shiftUp(int k) {
while (k>1 && datas[k/2].compareTo(datas[k])<0){ //与它的父节点进行比较
swap(k/2,k); //交换位置
k/=2;
}
}
private void shiftDown(int k){
while (2*k<=count){
int j=2*k;
if (j+1<=count && datas[j+1].compareTo(datas[j])>0)//两个子节点比较
j++;
if (datas[k].compareTo(datas[j])>=0)//父节点与较大子节点比较
break;
swap(k,j);
k=j;
}
}
插入一个元素（相当于增加一个索引并执行shiftUp操作）
public void insert(Item item){
assert count + 1<=capacity;
datas[count+1]=item;
count++;
shiftUp(count);
}
出队最大的元素(相当于将最大元素与第conut（conut为堆的长度）个元素进行交换，然后，进行shiftDown操作)
public Item extractMax(){
assert count>0;
Item ret=datas[1];
swap(1,count);
count--;
shiftDown(1);
return ret;
}
所有代码
public class MaxHeap {
protected Item[] datas;
protected int count;
private int capacity;
public MaxHeap(int capacity) {
this.capacity = capacity;
datas= (Item[]) new Comparable[capacity+1];
count=0;
}
public MaxHeap(Item[] arr,int n){
datas= (Item[]) new Comparable[n];
capacity=n;
for (int i = 0; i < arr.length ; i++)
datas[i+1]=arr[i];
count=n;
for (int i = count/2; i >=1; i--)
shiftDown(i);
}
public int size(){
return count;
}
public boolean isEmpty(){
return count == 0;
}
public void insert(Item item){
assert count + 1<=capacity;
datas[count+1]=item;
count++;
shiftUp(count);
}
public Item extractMax(){
assert count>0;
Item ret=datas[1];
swap(1,count);
count--;
shiftDown(1);
return ret;
}
private void shiftUp(int k) {
while (k>1 && datas[k/2].compareTo(datas[k])<0){
swap(k/2,k);
k/=2;
}
}
private void shiftDown(int k){
while (2*k<=count){
int j=2*k;
if (j+1<=count && datas[j+1].compareTo(datas[j])>0)
j++;
if (datas[k].compareTo(datas[j])>=0)
break;
swap(k,j);
k=j;
}
}
private void swap(int i, int count) {
Item t=datas[i];
datas[i]=datas[count];
datas[count]=t;
}
}
优先队列的优化
起因：上例实现的优先队列，显然需要创建新的空间。
解决方法：（总体使用数组的方式来解决）
当前堆的最大值与数组最后一个值进行交换
交换后，除最后一个元素其他的元素进行ShiftDown操作，保持前面部分依旧是一个最大堆
再重复所有步骤第一步操作
全部代码(ShiftDown函数与上次的例子不同的原因是因为索引值是从0开始，而不是从1开始)
public static void LocalMaxHeapFunc(Comparable[] arr){
//1.进行一次Heapify的过程
int n=arr.length;
//注意：其中我们的堆是从零开始索引的
//从（最后一个元素的索引-1）/2开始
//其中最后一个索引是n-1
for (int i = (n-1-1)/2; i >=0 ; i--) {
shiftDown(arr,n,i);
}
for (int i = n-1; i > 0; i--) {
Utils.swap2(arr,0,i);
shiftDown(arr,i,0);
}
}
private static void shiftDown(Comparable[] datas,int count,int k) {
while ((2*k+1)
int j=2*k+1;
if (j+1< count && datas[j+1].compareTo(datas[j])>0)
j++;
if (datas[k].compareTo(datas[j])>=0)
break;
Utils.swap2(datas,k,j);
k=j;
}
}
