我尝试基于此链接中的 unionNodes(BinomialHeapNode binHeap) 方法构建一个名为 union(BinomialHeap heap) 的函数，以帮助我将两个堆合并在一起。但是，当我尝试对其进行测试时，看起来 print 函数第二次返回 null以打印 heap1。更具体地说，我刚刚发现每次我在同一个堆上第二次调用 printHeap(BinomialHeap heap) 时，它什么都不会打印。我想知道发生了什么事。
我的联合方法：
public void union(BinomialHeap heap) {
if (heap.Nodes == null) {
return;
}
this.size += heap.size;
if (this.Nodes == null) {
this.Nodes = heap.Nodes;
return;
}
unionNodes(heap.Nodes);
}
我的打印方法：
/**
* Helper function to print the heap
* @param node heap node
* @param prev previous node of the current heap node
* @param direction 1 means that the current node is a left child node
* 2 means that the current node is a right sibling ndoe
*/
private void printHeapHelper(BinomialHeapNode node, BinomialHeapNode prev, int direction) {
while (node != null) {
if (direction == 1) {
System.out.println(String.format("%d(%d) is %d's child", node.key, node.degree, prev.key));
}
else {
System.out.println(String.format("%d(%d) is %d's sibling", node.key, node.degree, prev.key));
}
if (node.child != null) {
printHeapHelper(node.child, node, 1);
}
prev = node;
node = node.sibling;
direction = 2;
}
}
/**
* Function to print the heap
* @param heap input heap
*/
public void printHeap(BinomialHeap heap) {
if (heap == null) {
return;
}
BinomialHeapNode node = heap.Nodes;
System.out.print("Detailed Info of Binomial Heap ( ");
while (node != null) {
System.out.print(String.format("B%d ", node.degree));
node = node.sibling;
}
System.out.println("): ");
int i = 0;
while (heap.Nodes != null) {
i++;
System.out.println(String.format("\n%d, Binomial Heap B%d: ", i, heap.Nodes.degree));
System.out.println(String.format("%d(%d) is root", heap.Nodes.key, heap.Nodes.degree));
printHeapHelper(heap.Nodes.child, heap.Nodes, 1);
heap.Nodes = heap.Nodes.sibling;
}
}
上面链接中的相关方法：
class BinomialHeapNode
{
int key, degree;
BinomialHeapNode parent;
BinomialHeapNode sibling;
BinomialHeapNode child;
/* Constructor */
public BinomialHeapNode(int k)
{
key = k;
degree = 0;
parent = null;
sibling = null;
child = null;
}
}
class BinomialHeap
{
private BinomialHeapNode Nodes;
private int size;
/* Constructor */
public BinomialHeap()
{
Nodes = null;
size = 0;
}
/* Function to insert */
public void insert(int value)
{
if (value > 0)
{
BinomialHeapNode temp = new BinomialHeapNode(value);
if (Nodes == null)
{
Nodes = temp;
size = 1;
}
else
{
unionNodes(temp);
size++;
}
}
}
/* Function to unite two binomial heaps */
private void merge(BinomialHeapNode binHeap)
{
BinomialHeapNode temp1 = Nodes, temp2 = binHeap;
while ((temp1 != null) && (temp2 != null))
{
if (temp1.degree == temp2.degree)
{
BinomialHeapNode tmp = temp2;
temp2 = temp2.sibling;
tmp.sibling = temp1.sibling;
temp1.sibling = tmp;
temp1 = tmp.sibling;
}
else
{
if (temp1.degree < temp2.degree)
{
if ((temp1.sibling == null) || (temp1.sibling.degree > temp2.degree))
{
BinomialHeapNode tmp = temp2;
temp2 = temp2.sibling;
tmp.sibling = temp1.sibling;
temp1.sibling = tmp;
temp1 = tmp.sibling;
}
else
{
temp1 = temp1.sibling;
}
}
else
{
BinomialHeapNode tmp = temp1;
temp1 = temp2;
temp2 = temp2.sibling;
temp1.sibling = tmp;
if (tmp == Nodes)
{
Nodes = temp1;
}
else
{
}
}
}
}
if (temp1 == null)
{
temp1 = Nodes;
while (temp1.sibling != null)
{
temp1 = temp1.sibling;
}
temp1.sibling = temp2;
}
else
{
}
}
/* Function for union of nodes */
private void unionNodes(BinomialHeapNode binHeap)
{
merge(binHeap);
BinomialHeapNode prevTemp = null, temp = Nodes, nextTemp = Nodes.sibling;
while (nextTemp != null)
{
if ((temp.degree != nextTemp.degree) || ((nextTemp.sibling != null) && (nextTemp.sibling.degree == temp.degree)))
{
prevTemp = temp;
temp = nextTemp;
}
else
{
if (temp.key <= nextTemp.key)
{
temp.sibling = nextTemp.sibling;
nextTemp.parent = temp;
nextTemp.sibling = temp.child;
temp.child = nextTemp;
temp.degree++;
}
else
{
if (prevTemp == null)
{
Nodes = nextTemp;
}
else
{
prevTemp.sibling = nextTemp;
}
temp.parent = nextTemp;
temp.sibling = nextTemp.child;
nextTemp.child = temp;
nextTemp.degree++;
temp = nextTemp;
}
}
nextTemp = temp.sibling;
}
}
还有我的测试文件：
public class testBinomialHeap {
int[] input1 = new int[]{12, 7, 25, 15, 28, 33};
int[] input2 = new int[]{18, 35, 20, 42, 9, 31};
public void testInsert() {
BinomialHeap heap1 = new BinomialHeap();
for (int i = 0; i < input1.length; i++) {
heap1.insert(input1[i]);
}
System.out.println("Detailed info of heap1:");
heap1.printHeap(heap1);
}
public void testUnion() {
BinomialHeap heap1 = new BinomialHeap();
BinomialHeap heap2 = new BinomialHeap();
for (int i = 0; i < input1.length; i++) {
heap1.insert(input1[i]);
}
System.out.println("Detailed info of heap1:");
heap1.printHeap(heap1);
for (int i = 0; i < input2.length; i++) {
heap2.insert(input2[i]);
}
System.out.println("Detailed info of heap2:");
heap2.printHeap(heap2);
heap1.union(heap2);
System.out.println("Detailed info of heap1 after union:");
heap1.printHeap(heap1); // return null
}
public static void main(String[] args) {
testBinomialHeap test = new testBinomialHeap();
//test.testInsert();
test.testUnion();
}
}