0

I'm trying to implement a removeMax() method in this PQ class. The PQ is implemented with a singly-linked list. I can't seem to wrap my head around how you could scan the entire list for the largest value. Any guidance would be appreciated. Here's the whole class:

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());
    }

}
4

3 回答 3

0

java hasPriorityQueue , you dont have to impl yourself

see doc here http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

PQ is impl by HEAP http://en.wikipedia.org/wiki/Heap_(data_structure)

remove is O(lgn) no need to scan through

于 2013-10-31T03:57:53.243 回答
0

You know how to scan the list you do that in toString

The items extend comparable so you can compare them to each other.

Start with a max set to the first and iterate through compaing to max, if the value's greater set max to it.

Because you're doing a remove and the list is a single link one you'll need to remember the previous node to max too you'll need to set it's next to that of max afterwards.

Another approach is to scan down the list on insert and insert in order the the max is then always the first.

于 2013-10-31T04:18:41.550 回答
0

Generally when iterating through a linked list manually, you make a variable called walker and initialize it to first. Then you can do something like this

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

to traverse through the list. In your case, you'll need to keep track of the maximum value as you traverse.

To remove a value from a linked list, you "link around it", meaning that you set the previous node's next to the next of the value you're trying to remove. Since your list is singly-linked, you also need to keep track of the previous element as you go along, because otherwise you have a pointer to it after you decide which element you're removing.

Example:

aNode.next = aNode.next.next;

This removes the node aNode.next from your linked-list.

于 2013-10-31T04:25:08.190 回答