zak zak - 1 year ago 53

Java Question

In my program i have a collection of edges ,they have to be ordered by the weight.

Somewhere in the program i have to process the collection , and each time i have to remove the maximum of the collection.

I have already used an ArrayList but i'm looking for a better solution(time efficiency):

`public class Edge implements Comparable<Edge> {`

private int weight;

public void setWeight(int weight) {

this.weight = weight;**

}

@Override

public int compareTo(Edge o) {

return o.weight - this.weight;

}

}

what i did :

`private ArrayList<Edge> listOfEdges = new ArrayList<>();`

// i suppose here adding some edges in the list

Collections.sort(listOfEdges);

for (int i = 0; i < listOfEdges.size(); i++) {

System.out.println(listOfEdges.get(i).getWeight() + " ");

}

how can i get&remove the maximum of the list.

I have tested a treeSet but the edges can have the same weight, So what is the perfect Sorted Collection that accept a duplicate values.

Thank you

Answer Source

In my program i have a collection of edges ,they have to be ordered by the weight... I have already used an ArrayList but i'm looking for a better solution(time efficiency):

A binary tree like structure, such as a heap or priority queue, is what you are looking for. Once you have your object ordering (by the Comparable interface) specified, the maximum can be obtained in `O(1)`

time, and removed in `O(log n)`

time for `n`

edges.

how can i get&remove the maximum of the list.

peek and pop are the respective methods of a queue object implementation