zak zak zak zak - 23 days ago 8
Java Question

best collection for removing element

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

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

Comments