Java堆&优先级队列示例讲解(上)
1. 二叉树的顺序存储
1.1 存储方式
使用数组保存二叉树结构，方式即将二叉树用 层序遍历 方式放入数组中。
一般只适合表示完全二叉树，这种方式的主要用法就是堆的表示。
因为非完全二叉树会有空间的浪费（所有非完全二叉树用链式存储）。
1.2 下标关系
已知双亲 (parent) 的下标，则：
左孩子 (left) 下标 = 2 * parent + 1;
右孩子 (right) 下标 = 2 * parent + 2;
已知孩子（不区分左右） (child) 下标，则：
双亲 (parent) 下标 = (child - 1) / 2;
2. 堆(heap)
2.1 概念
1. 堆逻辑上是一棵完全二叉树
2. 堆物理上是保存在数组中
3. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
4. 反之，则是小堆，或者小根堆，或者最小堆
5. 堆的基本作用是，快速找集合中的 最值
2.2 操作-（下沉&上浮）本例是最大堆
元素下沉：
public void siftDown(int k){
//还存在子树
while (leftChild(k) < data.size()){
int j = leftChild(k);
//判断是否存在右子树且大于左子树的值
if(j+1 < data.size() && data.get(j+1) > data.get(j)){
j=j+1;
}
//此时j为左右子树最大值
//和当前节点比较大小
if(data.get(j) <= data.get(k)){
break;
}else {
swap(k,j);
k=j;
}
}
}
元素上浮：
// 上浮操作的终止条件: 已经走到根节点 || 当前节点值 <= 父节点值
// 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值
private void siftUp(int k) {
while (k>0 && data.get(k)>data.get(parent(k))){
swap(k,parent(k));
k=parent(k);
}
}
其中swap方法是交换操作：
//交换三连
private void swap(int i,int j) {
int temp = data.get(j);
data.set(j,data.get(i));
data.set(i,temp);
}
堆化数组：
public MaxHeap(int[] arr){
data = new ArrayList<>(arr.length);
// 1.先将arr的所有元素复制到data数组中
for(int i : arr){
data.add(i);
}
// 2.从最后一个非叶子结点开始进行siftDown
for (int i = parent(data.size()-1); i >=0 ; i--) {
siftDown(i);
}
}
图示：
以此数组为例：
// 调整前
int[] array = { 27,15,19,18,28,34,65,49,25,37 };
// 调整后
int[] array = { 15,18,19,25,28,34,65,49,27,37 };
时间复杂度分析：
最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度
即时间复杂度为 O(log(n))
2.3 建堆-完整代码（最大堆）
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class MaxHeap {
// 使用JDK的动态数组(ArrayList)来存储一个最大堆
List<Integer> data;
// 构造方法的this调用
public MaxHeap(){
this(10);
}
// 初始化的堆大小
public MaxHeap(int size){
data = new ArrayList<>(size);
}
public MaxHeap(int[] arr){
data = new ArrayList<>(arr.length);
// 1.先将arr的所有元素复制到data数组中
for(int i : arr){
data.add(i);
}
// 2.从最后一个非叶子结点开始进行siftDown
for (int i = parent(data.size()-1); i >=0 ; i--) {
siftDown(i);
}
}
public void add(int value){
//1.先直接加到堆的末尾
data.add(value);
//2.元素上浮操作
siftUp(data.size()-1);
}
public int peekMax (){
if(isEmpty()){
throw new NoSuchElementException("heap is empty!connot peek");
}
return data.get(0);
}
public int extractMax(){
// 取值一定注意判空
if(isEmpty()){
throw new NoSuchElementException("heap is empty!connot extract");
}
int max = data.get(0);
// 1.将数组末尾元素顶到堆顶
int lastValue =data.get(data.size()-1);
data.set(0,lastValue);
// 2.将数组末尾的元素删除
data.remove(data.size()-1);
// 3.进行元素的下沉操作
siftDown(0);
return max;
}
public void siftDown(int k){
//还存在子树
while (leftChild(k) < data.size()){
int j = leftChild(k);
//判断是否存在右子树且大于左子树的值
if(j+1 < data.size() && data.get(j+1) > data.get(j)){
j=j+1;
}
//此时j为左右子树最大值
//和当前节点比较大小
if(data.get(j) <= data.get(k)){
break;
}else {
swap(k,j);
k=j;
}
}
}
// 上浮操作的终止条件: 已经走到根节点 || 当前节点值 <= 父节点值
// 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值
private void siftUp(int k) {
while (k>0 && data.get(k)>data.get(parent(k))){
swap(k,parent(k));
k=parent(k);
}
}
//交换三连
private void swap(int i,int j) {
int temp = data.get(j);
data.set(j,data.get(i));
data.set(i,temp);
}
//判读堆为空
public boolean isEmpty(){
return data.size() == 0;
}
//根据索引找父节点
public int parent(int k){
return (k-1)>>1;
}
//根据索引找左孩子
public int leftChild(int k){
return k<<2+1;
}
//根据索引找右孩子
public int rightChild(int k){
return k<<2+2;
}
@Override
public String toString() {
return data.toString();
}
}
ps:随机数操作
int[] data=new int[10000];
//随机数
ThreadLocalRandom random = ThreadLocalRandom.current();
for (int i = 0; i < data.length; i++) {
data[i] = random.nextInt();
}
3. 优先级队列
详见下节：Java堆&优先级队列示例讲解(下)
到此这篇关于Java堆&优先级队列示例讲解(上)的文章就介绍到这了,更多相关Java 堆 优先级队列内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
