在 Java 中创建最小对象堆

Question

我正在尝试在 Java 中创建一个最小堆。我遵循了这个 site 上的算法。但是，在该站点上，他们传递的是整数，而我想传递对象。我的代码几乎可以工作，但我应该得到这个输出：

PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6

PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84

PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17

PARENT: 9 LEFT CHILD:22 RIGHT CHILD:10

但是我得到的是：

PARENT : 6 LEFT CHILD : 9 RIGHT CHILD :9

PARENT : 9 LEFT CHILD : 12 RIGHT CHILD :45

PARENT : 9 LEFT CHILD : 13 RIGHT CHILD :22

所以我遗漏了一些数字并且堆不正确。我已经看过所有内容，看起来它在逻辑上应该是相同的。我知道问题出在 MiniHeap.java，但我将我的所有代码都粘贴到了这个项目中以防万一。

MinHeap.java:

package javaapplication2;
public class MinHeap {
    
    private Node[] NHeap;
    private int size;
    private int maxsize;
 
    private static final int FRONT = 1;
 
    public MinHeap(int maxsize)
    {
        this.maxsize = maxsize;
        this.size = 0;
        NHeap = new Node[this.maxsize + 1];
    }
 
    private int parent(int pos)
    {
        return pos / 2;
    }
 
    private int leftChild(int pos)
    {
        return (2 * pos);
    }
 
    private int rightChild(int pos)
    {
        return (2 * pos) + 1;
    }
 
    private boolean isLeaf(int pos)
    {
        if (pos >=  (size / 2)  &&  pos <= size)
        { 
            return true;
        }
        return false;
    }
 
    private void swap(int fpos, int spos)
    {
        Node tmp;
        tmp = NHeap[fpos];
        NHeap[fpos] = NHeap[spos];
        NHeap[spos] = tmp;
        
 
    }
 
    private void minHeapify(int pos)
    {
        if (!isLeaf(pos))
        { 
            if ( NHeap[pos].getID() > NHeap[leftChild(pos)].getID()  || NHeap[pos].getID() > NHeap[rightChild(pos)].getID())
            {
                if (NHeap[leftChild(pos)].getID() < NHeap[rightChild(pos)].getID())
                {
                    swap(pos, leftChild(pos));
                    minHeapify(leftChild(pos));
                }else
                {
                    swap(pos, rightChild(pos));
                    minHeapify(rightChild(pos));
                }
            }
        }
    }
 
    public void insert(Node element)
    {
        NHeap[++size] = element;
        int current = size;
 
        while (NHeap[current].getID() < NHeap[parent(current)].getID())
        {
            swap(current,parent(current));
            current = parent(current);
        }   
    }
     public void first(Node element)
    {
        NHeap[0] = element; 
    }
    public void print()
    {
        for (int i = 1; i <= ((size/2)-1); i++ )
        {
            System.out.print(" PARENT : " + NHeap[i].getID() + " LEFT CHILD : " + NHeap[2*i].getID() 
                + " RIGHT CHILD :" + NHeap[2 * i  + 1].getID());
            System.out.println();
        } 
    }
 
    public void minHeap()
    {
        for (int pos = (size / 2); pos >= 1 ; pos--)
        {
            minHeapify(pos);
        }
    }
 
    public int remove()
    {
        int popped = NHeap[FRONT].getID();
        NHeap[FRONT] = NHeap[size--]; 
        minHeapify(FRONT);
        return popped;
    }
}

JavaApplication2.java:

package javaapplication2;
public class JavaApplication2 {
    public static void main(String[] args) {

        Node n = new Node();
        n.setID(5);
        Node n1 = new Node();
        n1.setID(45);
        Node n2 = new Node();
        n2.setID(17);
        Node n3 = new Node();
        n3.setID(10);
        Node n4 = new Node();
        n4.setID(84);
        Node n5 = new Node();
        n5.setID(19);
        Node n6 = new Node();
        n6.setID(6);
        Node n7 = new Node();
        n7.setID(22);
        Node n8 = new Node();
        n8.setID(9);
        
       
        System.out.println("The Min Heap is ");
        MinHeap minHeap = new MinHeap(15);
        minHeap.first(n);
        minHeap.insert(n1);
        minHeap.insert(n2);
        minHeap.insert(n3);
        minHeap.insert(n4);
        minHeap.insert(n5);
        minHeap.insert(n6);
        minHeap.insert(n7);
        minHeap.insert(n8);
        
      
        minHeap.print();
//        System.out.println("The Min val is " + minHeap.remove());
    }
    
}

Node.Java:

package javaapplication2;

public class Node {
        public int id;
    public int priority;
    public int timeSlice;
    
    public void setID(int newid){
        id = newid;
    }
    public int getID(){
        return id;
    }
}

Answer 1

您的 insert 函数中存在错误。

public void insert(Node element)
{
    NHeap[++size] = element;
    int current = size;

    while (NHeap[current].getID() < NHeap[parent(current)].getID())
    {
        swap(current,parent(current));
        current = parent(current);
    }   
}

因为您的第一个节点位于索引 1 处，所以每当节点向上移动到根节点时，这都会给您带来错误。那时，current 将等于 1，parent(current) 将 return 0。然后您将根元素与 NHeap[0].[=21 处的任何随机值进行比较=]

您需要确保 current 大于 1:

while (current > 1 && (NHeap[current].getId() < NHeap[parent(current)].getId())

您的 minHeapify 中也有错误。你有：

private void minHeapify(int pos)
{
    if (!isLeaf(pos))
    { 
        if ( NHeap[pos].getID() > NHeap[leftChild(pos)].getID()  || NHeap[pos].getID() > NHeap[rightChild(pos)].getID())
        {
            if (NHeap[leftChild(pos)].getID() < NHeap[rightChild(pos)].getID())
            {
                swap(pos, leftChild(pos));
                minHeapify(leftChild(pos));
            }else
            {
                swap(pos, rightChild(pos));
                minHeapify(rightChild(pos));
            }
        }
    }
}

但是如果NHeap[pos]没有权限child，这将索引超出堆中的有效项目。您将在堆中获得随机的东西。

解决这个问题的方法是确定哪个 children 是最小的，同时考虑到可能没有正确的 child 的可能性。然后比较最小的child和parent：

if (isLeaf(pos)) return;

int leftChild = leftChild(pos);
int rightChild = rightChild(pos);

int smallestChild = leftChild;
if (rightChild <= size && NHeap[rightChild] < NHeap[leftChild])
{
    smallestChild = rightChild;
}
if (NHeap[pos] > NHeap[smallestChild])
{
    swap(pos, smallestChild);
    minHeapify(smallestChild);
}

在 Java 中创建最小对象堆

Creating a Min Heap of Objects in Java

java

heap

data-structures