二叉堆
- 堆中任意节点的值总是不大于(不小于)其子节点的值
- 二叉堆是完全二叉树或者是近似完全二叉树
- 对于二叉堆中任意一个位置i,其左子节点为2i,右子节点为2i+1
1.优先队列
优先队列是一种用来维护一组元素构成的集合的数据结构 ,可以使用堆实现.
缺点:
- 无法知道元素在优先队列中的位置,因此无法直接访问对象,从而更新对象
如下最大优先队列:
- 插入元素时: 将元素集合构造成最大堆(上浮(swim):插入末尾,再上浮到正确位置)
- 取出元素时: 取出堆顶元素(最大值),然后将剩余元素更新为最大堆(下沉(sink): 将末尾元素放入顶部再下沉到正确位置)
- 这样每次取出元素都是最大值,便形成了最大优先队列
/**
* 使用二叉堆(最大堆)实现的最大优先队列
*
*/
public class MaxPQ<Key> {
private Object[] pq; //数组作为最大堆
private int N = 0; //记录元素个数
private int DEFAULT_N = 10; //初始大小
private Comparator<? super Key> comparator;
public MaxPQ(Comparator<? super Key> comparator){ //创建对象并传入比较器
pq = new Object[DEFAULT_N];
this.comparator = comparator;
}
//插入元素
public void insert(Key key){
//自动扩展1.5倍
if(N == DEFAULT_N-1) adjust(DEFAULT_N+=DEFAULT_N>>>1);
pq[++N] = key;
swim(N);
}
public Key max(){ return (Key)pq[1]; }
//删除并返回最大元素
public Key delMax(){
//自动缩减一半
if(N>10 && N < DEFAULT_N/3) adjust(DEFAULT_N>>>=1);
Key max = (Key)pq[1];
pq[1] = pq[N];
pq[N--] = null;
sink(1);
return max;
}
//返回优先队列中元素个数
public int size(){ return N; }
public boolean isEmpty(){ return N == 0;}
/**
*上浮: 将元素上浮到优先队列正确位置(构造最大堆)
*步骤: 1.将arr[k]元素与其父节点arr[2*k]比较,如果大于父节点就交换
* 2.重复步骤1直到arr[k]上浮到正确位置
*/
public void swim(int k){
while(k>1 && !less(k,k>>>1)) exch(k, k>>>=1);
}
/**
*下沉: 将元素下沉到优先队列正确位置(构造最大堆)
*步骤: 1.将arr[k]元素与其子节点中较大的元素arr[j]比较,如果子节点较大就交换
* 2.重复步骤1直到下沉到正确位置
*/
public void sink(int k){
while(k<<1 <= N){
int j = k<<1;
if(j < N && less(j,j+1)) ++j;
if(less(k,j)) exch(k,j);
k = j;
}
}
//交换
public void exch(int i,int j){
Key temp = (Key)pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
//比较
public boolean less(int i,int j){
return comparator.compare((Key)pq[i],(Key)pq[j]) < 0;
}
//调整优先队列大小
public void adjust(int length){
Object[] pqN = new Object[length];
System.arraycopy(pq,1,pqN,1,N);
pq = pqN;
}
}2.索引优先队列
在优先队列的基础上进行改进
- 加入一个索引数组qp,其值记录了元素在优先队列pq中的位置,从而可以访问优先队列中的元素,更新元素
- 索引优先队列pq中保存元素的索引,元素数组keys保存元素
实现: 在优先队列的基础上,同步更新索引数组qp丶元素数组keys以及他们之间的映射关系(pq[qp[i]] = i)即可
/**
* 索引优先队列
*/
public class IndexMaxPQ<Key> {
private int[] pq; //最大堆,下标为元素位置,值是元素的索引
private int[] qp; //索引数组,下标是元素的索引,值为元素在最大堆pq中的位置,索引为i则 pq[qp[i]] = i
private Object[] keys; //对象数组,下标为元素索引,值为元素
private int n = 0; //记录元素个数
private Comparator<? super Key> comparator; //比较器
//构造方法-传入比较器
public IndexMaxPQ(int maxN,Comparator<? super Key> comparator){
this.comparator = comparator;
pq = new int[maxN+1];
qp = new int[maxN+1]; //初始化默认值为0
keys = new Object[maxN+1];
}
//构造方法-使用默认比较器
public IndexMaxPQ(int maxN){
comparator = (Key x,Key y) -> {
if(x instanceof Comparable)
return ((Comparable) x).compareTo(y);
throw new RuntimeException("须传入比较器或者实现Comparable接口");
};
pq = new int[maxN+1];
qp = new int[maxN+1]; //初始化默认值为0
keys = new Object[maxN+1];
}
//插入索引为k的元素e
public void insert(int k,Key e){
pq[++n] = k;
qp[k] = n;
keys[k] = e;
swim(n);
}
//删除最大元素并返回索引
public int delMax(){
int maxIndex = pq[1];
exch(1,n--);
sink(1);
//删除映射
pq[n+1] = -1;
qp[maxIndex] = -1;
keys[maxIndex] = null;
return maxIndex;
}
//获取指定索引的值
public Key peek(int k){ return (Key)keys[k]; }
//将索引k的元素设置为key
public void change(int k,Key e){
keys[k] = e;
//更新
sink(qp[k]);
swim(qp[k]);
}
//是否存在索引为k的元素
public boolean contains(int k){
return k>=0 && k <= qp.length && qp[k]>0 && qp[k]<=n;
}
//删除索引k及相关元素
public void delete(int k){
exch(qp[k],n--);
sink(qp[k]);
swim(qp[k]);
//删除映射
pq[n+1] = -1;
qp[k] = -1;
keys[k] = null;
}
//返回最大元素
public Key maxKey(){ return (Key)keys[pq[1]]; }
//返回最大元素的索引
public int maxIndex(){ return pq[1]; }
public boolean isEmpty(){ return n==0; }
public int size(){ return n; }
//上浮
public void swim(int k){
while(k > 1 && less(k>>>1,k)) exch(k,k>>>=1);
}
//下沉
public void sink(int k){
while(k<<1 <= n){
int j = k<<1;
if(j<n && less(j,j+1)) ++j;
if(less(k,j)) exch(k,j);
k = j;
}
}
public void exch(int i, int j){
if(i == j) return;
//堆:交换
pq[i] = pq[i] ^ pq[j];
pq[j] = pq[i] ^ pq[j];
pq[i] = pq[i] ^ pq[j];
//更新索引数组
qp[pq[i]] = i;
qp[pq[j]] = j;
}
public boolean less(int i,int j){
return comparator.compare((Key)keys[pq[i]],(Key)keys[pq[j]]) < 0;
}
}3.原地堆排序
*概述: *
- 使用下沉将数组构造为一个最大优先队列(最大堆)(即: 从堆底最后一个非叶子节点开始逐个下沉构造堆)
- 依次将堆顶元素(最大值)与数组末尾元素交换
- 将数组中剩余元素(除了交换到末尾的最大值元素)更新为优先队列(交换后的堆顶元素下沉构造堆)
- 重复步骤2,步骤3直到堆大小为1结束
/**
* 原地堆排序
*/
public void heapSort(int[] arr){//0索引不使用
int n = arr.length-1;
//1.构造堆
for(int i=n>>>1;i>0;--i) //最后一个节点(n)的父节点(n/2)为最后一个非叶子节点
sink(arr,i,n);
//2.将堆顶元素(最大元素)放入数组尾部,然后对新的堆顶元素进行下沉构造堆
while(n > 1){
exch(arr,1,n--);
sink(arr,1,n);
}
}
/**
* 下沉: 将元素arr[k]下沉构造堆,堆结尾为arr[n]
* 即: 如果arr[k]比其子节点中较大的元素arr[j]小,则与其交换
*/
public void sink(int[] arr,int k,int n){
while(k<<1 <= n){
int j = k<<1;
if(j<n && arr[j]<arr[j+1]) ++j;
if(arr[k] < arr[j]) exch(arr,k,j);
k = j;
}
}
//交换
public void exch(int[] arr,int i,int j){
if(i == j) return;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}4.堆排序优化
*概述: *
原地堆排序时,通过将数组末尾元素与堆顶元素交换,然后arr[1]下沉到正确位置更新堆,
显然arr[1]的正确位置更大概率接近堆底,然而下沉时每次都比较是否到达正确位置,
因此可以直接下沉到堆底,不在进行比较,再通过上浮时比较是否到达正确位置,这样减少比较
对比:
1. 优点: 与原地堆排序相比减少了很多比较,当比较代价较大时,有优势
2. 缺点: 与原地堆排序相比增加了额外空间
/**
* 堆排序优化
*/
public void heapSort(int[] arr){
int n = arr.length - 1;
for(int i=n>>>1;i>0;--i) //下沉构造堆
sink(arr,i,n);
while(n > 1){
exch(arr,1,n--);
int k = sinkD(arr,1,n); //直接下沉返回其位置k
swim(arr,k); //将其上浮到正确位置
}
}
//上浮
public void swim(int[] arr,int k){
while(k > 1 && arr[k] > arr[k>>>1]) exch(arr,k,k>>>=1);
}
//下沉: 将arr[k]下沉到堆中正确位置
public void sink(int[] arr,int k, int n){
while(k<<1 <= n){
int j = k << 1;
if(j < n && arr[j] < arr[j+1]) ++j;
if(arr[k] < arr[j]) exch(arr,k,j);
k = j;
}
}
//直接下沉: 不判断是否到达正确位置,将arr[k]直接下沉到堆底,并返回此时索引k
public int sinkD(int[] arr,int k,int n){
int temp = arr[k];
while(k<<1 <= n){
int j = k<<1;
if(j < n && arr[j] < arr[j+1]) ++j;
arr[k] = arr[j];
k = j;
}
arr[k] = temp;
return k;
}
//交换
public void exch(int[] arr,int i,int j){
if(i == j) return;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}