Java 数据结构与算法系列精讲之二叉堆

Java 数据结构与算法系列精讲之二叉堆

目录概述优先队列二叉堆二叉堆实现获取索引添加元素siftUp完整代码

概述

从今天开始, 小白我将带大家开启 java 数据结构 & 算法的新篇章.

优先队列

优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图:

二叉堆

二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图:

二叉堆实现

获取索引

// 获取父节点的索引值

public int parent(int index) {

if (index <= 0) {

throw new RuntimeException("Invalid Index");

}

return (index - 1) / 2;

}

// 获取左孩子节点索引

public int leftChild(int index) {

return index * 2 + 1;

}

// 获取右孩子节点索引

public int rightChild(int index) {

return index * 2 + 2;

}

添加元素

// 添加元素

public void add(E e) {

data.add(e);

http:// siftUp(data.size() - 1);

}

siftUp

// siftDown

private void siftDown(int k) {

while (leftChild(k) < data.size()) {

int j = leftChild(k);

if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {

j++;

}

if (data.get(k).compareTo(data.get(j)) >= 0) {

break;

}

Collections.swap(data, k, j);

EnnTIi k = j;

}

}

完整代码

import java.util.ArrayList;

import java.util.Collections;

public class BinaryHeap> {

private ArrayList data;

// 无参构造

public BinaryHeap() {

data = new ArrayList<>();

}

// 有参构造

public BinaryHeap(int capacity) {

data = new ArrayList<>(capacity);

}

// 或者元素个数

public int size() {

return data.size();

}

// 判断堆是否为空

public boolean isEmpty() {

return data.isEmpty();

}

// 获取父节点的索引值

public int parent(int index) {

if (index <= 0) {

throw new RuntimeException("Invalid Index");

}

http:// return (index - 1) / 2;

}

// 获取左孩子节点索引

public int leftChild(int index) {

return index * 2 + 1;

}

// 获取右孩子节点索引

public int rightChild(int index) {

return index * 2 + 2;

}

// 添加元素

public void add(E e) {

data.add(e);

siftUp(data.size() - 1);

}

// siftUp

private void siftUp(int k) {

while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {

Collections.swap(data, k, parent(k));

k = parent(k);

}

}

// siftDown

private void siftDown(int k) {

while (leftChild(k) < data.size()) {

int j = leftChild(k);

if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {

j++;

}

if (data.get(k).compareTo(data.get(j)) >= 0) {

break;

}

Collections.swap(data, k, j);

k = j;

}

}

}

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