Java堆&优先级队列示例讲解(上)

Java堆&优先级队列示例讲解(上)

目录1. 二叉树的顺序存储1.1 存储方式1.2 下标关系2. 堆(heap)2.1 概念2.2 操作-（下沉&上浮）本例是最大堆2.3 建堆-完整代码（最大堆）3. 优先级队列

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. http://堆的基本作用是，快速找集合中的 最值

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);

}

堆化数组：

/**

http:// * 将任意数组堆化

* @param arr

*/

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 建堆-完整代码（最大堆）

/**

* 基于整形最大堆实现

* 时根节点从0开始编号,若此时节点编号为k

* 左孩子为2k+1

* 右孩子为2k+2

* 父节点为（k-1）/2

*/

import java.util.ArrayList;

import java.util.List;

import java.util.NoSuchElementException;

public class MaxHeap {

// 使用JDK的动态数组(ArrayList)来存储一个最大堆

List data;

// 构造方法的this调用

public MaxHeap(){

this(10);

}

// 初始化的堆大小

public MaxHeap(int size){

data = new ArrayList<>(size);

}

/**

* 将任意数组堆化

* @param arr

*/

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);

}

}

/**

* 向最大堆中增加值为Value的元素

* @param value

wARkKIfh */

public void add(int value){

//1.先直接加到堆的末尾

data.add(value);

//2.元素上浮操作

siftUp(data.size()-1);

}

/**

* 只找到堆顶元素值

* @return

*/

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.ghttp://et(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堆&优先级队列示例讲解(下)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。