斐波那契堆 java
时间: 2023-11-04 20:54:06 浏览: 45
斐波那契堆是一种数据结构,用于实现优先级队列。下面是一个简单的斐波那契堆的 Java 实现:
```java
import java.util.*;
public class FibonacciHeap<T> {
private Node<T> maxNode;
private int size;
// 节点定义
private static class Node<T> {
T key;
int degree;
boolean marked;
Node<T> parent;
Node<T> child;
Node<T> left;
Node<T> right;
public Node(T key) {
this.key = key;
left = this;
right = this;
}
}
// 插入节点
public void insert(T key) {
Node<T> node = new Node<>(key);
if (maxNode != null) {
node.left = maxNode;
node.right = maxNode.right;
maxNode.right = node;
node.right.left = node;
if (compare(node, maxNode) > 0) {
maxNode = node;
}
} else {
maxNode = node;
}
size++;
}
// 合并两个斐波那契堆
private void merge(FibonacciHeap<T> other) {
if (other.maxNode == null) {
return;
}
if (maxNode == null) {
maxNode = other.maxNode;
size = other.size;
return;
}
Node<T> leftNode = maxNode.left;
Node<T> rightNode = other.maxNode.right;
maxNode.left = rightNode;
rightNode.left = leftNode;
leftNode.right = rightNode;
rightNode.right = maxNode;
if (compare(other.maxNode, maxNode) > 0) {
maxNode = other.maxNode;
}
size += other.size;
}
// 提取最大节点
public T extractMax() {
Node<T> max = maxNode;
if (max != null) {
// 将最大节点的子节点移动到根列表中
Node<T> child = max.child;
while (child != null) {
Node<T> nextChild = child.right;
child.left = maxNode;
child.right = maxNode.right; maxNode.right = child;
child.right.left = child;
child.parent = null;
child = nextChild;
}
// 从根列表中移除最大节点
max.left.right = max.right;
max.right.left = max.left;
if (max == max.right) {
maxNode = null;
} else {
maxNode = max.right;
consolidate();
}
size--;
return max.key;
}
return null;
}
// 合并度数相同的树
private void consolidate() {
int maxSize = (int) Math.floor(Math.log(size) / Math.log(2)) + 1;
List<Node<T>> degreeTable = new ArrayList<>(maxSize);
for (int i = 0; i < maxSize; i++) {
degreeTable.add(null);
}
List<Node<T>> roots = new ArrayList<>();
Node<T> current = maxNode;
Node<T> start = maxNode;
do {
roots.add(current);
current = current.right;
} while (current != start);
for (Node<T> root : roots) {
Node<T> node = root;
int degree = node.degree;
while (degreeTable.get(degree) != null) {
Node<T> other = degreeTable.get(degree);
if (compare(node, other) < 0) {
Node<T> temp = node;
node = other;
other = temp;
}
link(other, node);
degreeTable.set(degree, null);
degree++;
}
degreeTable.set(degree, node);
}
maxNode = null;
for (Node<T> root : roots) {
if (root != null) {
if (maxNode == null) {
maxNode = root;
} else {
if (compare(root, maxNode) > 0) {
maxNode = root;
}
}
}
}
}
// 连接两个节点
private void link(Node<T> child, Node<T> parent) {
child.left.right = child.right;
child.right.left = child.left;
child.parent = parent;
if (parent.child == null) {
parent.child = child;
child.right = child;
child.left = child;
} else {
child.left = parent.child;
child.right = parent.child.right;
parent.child.right = child;
child.right.left = child;
}
parent.degree++;
child.marked = false;
}
// 比较节点
private int compare(Node<T> x, Node<T> y) {
return ((Comparable<T>) x.key).compareTo(y.key);
}
// 获取堆的大小
public int getSize() {
return size;
}
}
```