java如何从PQ（单链表）中删除最大值

Question

我试图在这个PQ类中实现一个removeMax（）方法。PQ通过单链表实施。我似乎不知道你如何扫描整个列表以获得最大的价值。任何指导都将不胜感激。下面是全班同学：

import java.util.NoSuchElementException;


public class UnorderedLinkedListMaxPQ<Item extends Comparable<Item>> {
private int N;
private Node first;   

private class Node {
    private Item item;
    private Node next;
}

public UnorderedLinkedListMaxPQ() {
    first = null;
    N = 0;
}

public boolean isEmpty() {
    return N == 0;
}

public int size() {
    return N;
}


public void insert(Item item) {
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
    N++;
}

public Item removeMax() {
    if (isEmpty()) { throw new NoSuchElementException("PQ underflow"); }
    else if (N == 1) {
       Item item = first.item;
       first = first.next;
       N--;
       return item;
    }
    else if (N != 0) {
      // ?
    }
}

public String toString() {
    Node counter = first;
    String string = "";
    while (counter != null) {
        string = string + counter.item + ", ";
        counter = counter.next;
    }
    return string;   
}

private boolean less(Item v, Item w) {
    return (v.compareTo(w) < 0);
}


public static void main(String[] args) {
    UnorderedLinkedListMaxPQ<Integer> pq = new UnorderedLinkedListMaxPQ<Integer>();
    pq.insert(32);
    pq.insert(7);
    pq.insert(18);
    pq.insert(2);
    StdOut.println("The priority queue contains (" + pq.toString() + "). \n");
    while (!pq.isEmpty())
        StdOut.println(pq.removeMax());
    }

}

Answer 1

在toString中，你知道如何扫描列表

这些项目具有可比性，因此可以相互比较

从最大值设置为第一个开始，如果该值更大，则循环比较最大值

因为你正在做一个移除，而列表是一个单链接，你需要记住max之前的节点，之后你需要将它设置为max的旁边

另一种方法是在insert和insert上向下扫描列表，以便最大值总是第一个

Answer 2

java有PriorityQueue，你不需要自己

见这里的医生 http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

PQ是按堆执行的 http://en.wikipedia.org/wiki/Heap_(data_structure)

移除是O（lgn）无需扫描

Answer 3

通常，在手动遍历链表时，会生成一个名为walker的变量，并将其初始化为first。然后你可以做这样的事情

while (walker != null) {
    // Do something
    walker = walker.next;
}

浏览列表。在您的情况下，您需要在遍历时跟踪最大值

要从链表中删除一个值，可以“围绕它链接”，这意味着将前一个节点的next设置为要删除的值的next。由于列表是单独链接的，所以在执行过程中还需要跟踪上一个元素，否则在决定要删除哪个元素后，就会有一个指向它的指针

例如：

aNode.next = aNode.next.next;

这将移除节点阳极。下一步从你的链接列表