java - PriorityQueue based on unsorted array iterator -
i have written own priority_queue based on unsorted array, adding new element works fast in o(1) removing element max priority(minimal value) works slow in o(n)
import java.util.*; public class priorityqueue<k extends comparable> { private int index; private comparable[] elements; public object[] getelements() { return elements; } public priorityqueue(int capacity) { if (capacity < 0) capacity = 10; elements = new comparable[capacity]; } public priorityqueue() { this(10); } public boolean isempty() { return index == 0; } public int size() { return index; } private void resize() { elements = arrays.copyof(elements, elements.length * 2); } public void add(k element) { if (index == elements.length) resize(); elements[index++] = element; } public comparable remove() { if (isempty()) throw new priorityqueueisemptyexception("queue empty!"); int priorityindex = 0; (int = 1; < index; i++) { if (elements[i].compareto(elements[priorityindex]) < 0) priorityindex = i; } comparable result = elements[priorityindex]; index--; elements[priorityindex] = elements[index]; return result; } public comparable<k> poll() { if (isempty()) return null; return remove(); } public comparable element() { if (isempty()) throw new priorityqueueisemptyexception("queue empty!"); int priorityindex = 0; (int = 1; < index; i++) { if (elements[i].compareto(elements[priorityindex]) < 0) priorityindex = i; } return elements[priorityindex]; } public comparable peek() { if (isempty()) return null; return element(); } public iterator iterator() { return new queueiterator(); } public void print() { (int = 0; < index; i++) { system.out.print(elements[i] + " --> "); } system.out.println(); } private class queueiterator implements iterator { // keep list of indexes of elements have been taken allready method next() // keep in order not check elements such indexes when founding new min element // sorry eng private list<integer> usedindexes; private comparable next; public queueiterator() { usedindexes = new arraylist<integer>(); } private comparable min(comparable[] elements, int from, int to, list<integer> usedindexes) { // trick assign min value // cannot start first element cause might minimal allready int startindex = from; (int = from; <= to; i++) { if (!usedindexes.contains(i)) { startindex = i; break; } } comparable min = elements[startindex]; int minindex = startindex; (int = from; <= to; i++) { if (!usedindexes.contains(i) && elements[i].compareto(min) < 0) { min = elements[i]; minindex = i; } } usedindexes.add(minindex); return min; } @override public boolean hasnext() { return usedindexes.size() == index; } @override public comparable next() { if (isempty()) throw new nosuchelementexception(); next = min(elements, 0, index - 1, usedindexes); return next; } @override public void remove() { throw new unsupportedoperationexception(); } } } public class priorityqueueisemptyexception extends runtimeexception { priorityqueueisemptyexception() { } priorityqueueisemptyexception(string message) { super(message); } } my questions are: had made iterator right? seems me not method next(), works in o(n * n), right? there way iterator better?
Comments
Post a Comment