gpt4 book ai didi

Java最小堆优先级队列实现

转载 作者:塔克拉玛干 更新时间:2023-11-02 20:00:32 25 4
gpt4 key购买 nike

我目前正在尝试实现一个最小堆 PQ,但是我在实现的正确性方面遇到了一些问题,我似乎无法弄清楚我做错了什么 - 它没有输出最低优先级或正确排序。

    public void AddItem(Vertex item)
{
if (queueSize == QueueArray.length)
{
Vertex[] QueueArray2 = new Vertex[queueSize*2];
System.arraycopy(QueueArray, 0, QueueArray2, 0, queueSize);
QueueArray = QueueArray2;
}

if (queueSize == 0)
{
QueueArray[queueSize] = item; // insert at 0
queueSize++;
}
else
{
int index=queueSize;
//Vertex newNode = new Vertex(item, priority);
QueueArray[index] = item;
queueSize++;

int parent=(index-1)/2;
while (index!=0 && QueueArray[index].getF()<QueueArray[parent].getF())
{
// swap parent and index items
Vertex temp = QueueArray[parent];
QueueArray[parent] = QueueArray[index];
QueueArray[index] = temp;

index=parent;
parent=(index-1)/2;
}
}
}


public Vertex GetNextItem()
{
if (queueSize == 0)
{
return null;
}
Vertex temp = QueueArray[0];
--queueSize;
if (queueSize > 0)
{
QueueArray[0] = QueueArray[queueSize];
swapNodes(0);
}
QueueArray[queueSize] = null;
return temp;
}

public void swapNodes(int root)
{
int child;
if ((2*root+1) >= queueSize)
{
child = root; //no children
}
else
if ((2*root)+2 == queueSize)
{
child = (2*root)+1;
}
else
if (QueueArray[(2*root)+1].getF()< QueueArray[(2*root)+2].getF())
{
child = (2*root)+1; //left child
}
else
{
child = (2*root)+2; //right child
}
//swap the nodes around
if (QueueArray[root].getF() < QueueArray[child].getF())
{
Vertex temp = QueueArray[root];
QueueArray[root] = QueueArray[child];
QueueArray[child] = temp;
swapNodes(child);
}
}

使用以下测试数据:

data1.setF(71);
data2.setF(19);
data3.setF(65);
data4.setF(16);
data5.setF(14);
data6.setF(8);
data7.setF(10);
data8.setF(36);
data9.setF(543);
test.AddItem(data1);
test.AddItem(data2);
test.AddItem(data3);
test.AddItem(data4);
test.AddItem(data5);
test.AddItem(data6);
test.AddItem(data7);
test.AddItem(data8);
test.AddItem(data9);

我得到以下结果:

Array data: 8.0 
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
Array data: 14.0
Array data: 71.0
Array data: 543.0
PQ data: 8.0
PQ data: 543.0
PQ data: 71.0
PQ data: 14.0
PQ data: 65.0
PQ data: 19.0
PQ data: 36.0
PQ data: 16.0
PQ data: 10.0

我希望结果按升序排列 - 起初我认为这可能是由于交换了错误的 child ,但后来最后的输出是最高优先级,所以这没有意义。我花了几个小时尝试研究堆优先级队列,但找不到任何帮助。

编辑:

这是 CMPS 要求的更好的代码输出(我想这就是你要求的)

Array data: 8.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
Array data: 14.0
Array data: 71.0
Array data: 543.0
PQ GetNextItem: 8.0

Array data: 543.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
Array data: 14.0
Array data: 71.0
PQ GetNextItem: 543.0

Array data: 71.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
Array data: 14.0
PQ GetNextItem: 71.0

Array data: 14.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
PQ GetNextItem: 14.0

Array data: 65.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
PQ GetNextItem: 65.0

Array data: 19.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
PQ GetNextItem: 19.0

Array data: 36.0
Array data: 16.0
Array data: 10.0
PQ GetNextItem: 36.0

Array data: 16.0
Array data: 10.0
PQ GetNextItem: 16.0

Array data: 10.0
PQ GetNextItem: 10.0

最佳答案

当你在移除节点后在堆中向下冒泡时,你需要最小值在顶部,但在下面的代码中,如果最小值在顶部,则交换,这应该是相反的。

改变:

     if (QueueArray[root].getF() < QueueArray[child].getF())
{
Vertex temp = QueueArray[root];
QueueArray[root] = QueueArray[child];
QueueArray[child] = temp;
swapNodes(child);
}

收件人:

      if (QueueArray[root].getF() > QueueArray[child].getF())
{
Vertex temp = QueueArray[root];
QueueArray[root] = QueueArray[child];
QueueArray[child] = temp;
swapNodes(child);
}

关于Java最小堆优先级队列实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29392938/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com