1 
public class Link {
public int weight;
public int loc;
public Link next;
public boolean visited;
public Link parent;

public Link(int d, int loc){
    this.weight = d;
    this.loc = loc;
    this.visited = false;
}
public Link(Link p, int d, int loc){
    this.parent = p;
    this.weight = d;
    this.loc = loc;
}

public void printLink(){
    System.out.println(weight);
}
}

class LinkList{


public Link first;

public LinkList(){
    first = null;
}
public void add(int d, int loc){
    Link link = new Link(d, loc);
    if (first == null){
        first = link;
    }
    else{
        Link curr = first;
        while (curr.next!=null){
            curr = curr.next;
        }
        curr.next = link;
    }

}
public void printList(){
    Link currentLink = first;
    System.out.println("List: ");
    while(currentLink != null) {
        currentLink.printLink();
        currentLink = currentLink.next;
    }
    System.out.println("");
}
public boolean isEmpty(){
    return first == null;
}
public Link delete(){
    Link temp = first;
    first = first.next;
    return temp;
}

}

 public class MinHeap {
    public Link[] Heap;
    public int size;
    public int maxsize;

    private static final int FRONT = 0;

    public MinHeap(int maxsize, Link x)
    {
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new Link[this.maxsize + 1];
        Heap[0] = x;
    }

    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)
    {
        Link tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }

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

    public void add(Link element)
    {
        Heap[++size] = element;
        int current = size;

        while (Heap[current].weight < Heap[parent(current)].weight)
        {
            swap(current,parent(current));
            current = parent(current);
        }   
    }

    public void print()
    {
        for (int i = 1; i <= size / 2; i++ )
        {
            System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i] 
                + " RIGHT CHILD :" + Heap[2 * i  + 1]);
            System.out.println();
        } 
    }

    public void minHeap()
    {
        for (int pos = (size / 2); pos >= 1 ; pos--)
        {
            minHeapify(pos);
        }
    }
    public boolean inQ(Link d){
        int x = d.weight;
        for (int i = 0; i<size;i++){
            if (Heap[i].weight == x){
                return true;
            }
        }
        return false;
    }

    public Link remove()
    {
        Link popped = Heap[FRONT];
        Heap[FRONT] = Heap[size--]; 
        minHeapify(FRONT);
        return popped;
    }
}

我这里有一个最小堆类，它根据权重属性存储 Link 对象。我的目标是能够直接访问和更改存储在最小堆中的对象的属性。我需要能够仅基于“loc”属性访问这些对象。
因此，例如，我可能想要访问 loc 值为 6 的 Link 对象并更改其父属性或权重属性；但是我只知道它在访问时的 loc 属性值。
我的理解是我应该使用指向这些对象的指针数组，但我不确定我将如何实现它。

谢谢！

4

1 回答 1

0

根据您的代码，您是每个链接都知道其父级以及列表中的下一个元素。

您应该遵循以下算法并更新必填字段。

  1. 首先将链接对象和 loc 值传递给将更新权重/父级的方法。您可以编写两种方法，一种用于更新权重，另一种用于更新权重，或者您可以使用一种方法并使用标志来隔离活动。

  2. 如果要更新权重，很简单。

  3. 如果要更新父对象，则必须将新的父对象也传递给该方法，因为您也应该更新父对象的下一个对象，但请确保正确处理代码，因为您可能会丢失父对象的现有下一个对象。

当您传递实际对象时，jvm 将保持不变。确保不要传递列表的权重/父级的值。

于 2015-04-04T05:42:20.347 回答