总结
再讲堆和堆排序之前先讲优先队列
优先队列
- 优先队列是什么:
与常见的队列不同的是，优先队列并不遵循“先进先出”的原则，反而是根据优先级来确定是否先出。优先级高的先出，优先级低的后出。 - 为什么使用优先队列:
优先队列是用在，处理动态的数据排序。也就是优先队列所处理的数据可能时刻在变化的。
例子：医院排队，病情紧急的病人，先去治疗。该情景中：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<Item extends Comparable> {
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<Item extends Comparable> {
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)<count){
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;
}
}
