Priority Queues/ADT - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:44:00Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:44, 9 October 2019
Line 17:		Line 17:
	==Java Code==		==Java Code==

	Link: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/		Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/

	===Priority queue interface===		===Priority queue interface===

Admin: /* Priority queue interface */

2017-06-23T04:46:03Z

Priority queue interface

← Older revision		Revision as of 04:46, 23 June 2017
Line 54:		Line 54:
	}		}
	</pre>		</pre>


	===Abstract class===		===Abstract class===

Admin: /* Abstract class */

2017-06-22T22:35:40Z

Abstract class

@@ Line 59: / Line 59: @@
 <pre>
 /** Priority Queue ADT.
+  *
@@ Line 70: / Line 75: @@
 			implements PriorityQueue<K,V> {
-	protected static class PQEntry<K,V> implements Entry<K,V> {
+	protected static class Item<K,V> {
 		private K k;
 		private V v;
-		public PQEntry(K key, V value) {
+		public Item(K key, V value) {
 			this.k = key; this.v = value;
+		}
 		/** Return the key associated with this element. */
 		public K getKey() { return k; }
 		/** Return the value associated with this element. */
 		public V getValue() { return v; }
 		/** Set the key associated with this element. */
@@ Line 92: / Line 94: @@
 		protected void setValue(V v) { this.v = v; }
+	}
+}
 </pre>

Admin: /* Code */

2017-06-22T21:01:07Z

Code

← Older revision		Revision as of 21:01, 22 June 2017
Line 15:		Line 15:
	See code below for more information.		See code below for more information.

	==Code==		==Java Code==

	Link: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/		Link: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/
Line 96:		Line 96:
	}		}
	</pre>		</pre>



	==Flags==		==Flags==

Admin: /* Notes */

2017-06-22T21:00:51Z

Notes

← Older revision		Revision as of 21:00, 22 June 2017
Line 3:		Line 3:
	Background on what a priority queue is: [[Priority Queues]]		Background on what a priority queue is: [[Priority Queues]]

	Background on what abstract data types are: [[Abstract Data Types]		Background on what abstract data types are: [[Abstract Data Types]]

	The priority queues abstract data type can be implemented with two components: an interface, and an abstract class.		The priority queues abstract data type can be implemented with two components: an interface, and an abstract class.

Admin at 21:00, 22 June 2017

2017-06-22T21:00:41Z

@@ Line 1: / Line 1: @@
 Background on what a priority queue is: [[Priority Queues]]
@@ Line 94: / Line 96: @@
+}
 </pre>

Admin: Created page with "Background on what a priority queue is: Priority Queues Background on what abstract data types are: [[Abstract Data Types] The priority queues abstract data type can be..."

2017-06-22T21:00:08Z

Created page with "Background on what a priority queue is: Priority Queues Background on what abstract data types are: [[Abstract Data Types] The priority queues abstract data type can be..."

New page

Background on what a priority queue is: [[Priority Queues]]

Background on what abstract data types are: [[Abstract Data Types]

The priority queues abstract data type can be implemented with two components: an interface, and an abstract class.

The first component is an interface, which is an "inheritance-lite" way of specifying methods that a priority queue must implement, but without providing or specifying any further details. This can be thought of as a ''purely'' abstract class - there is absolutely nothing concrete that can be defined in the interface. (See also: [[Java/Interfaces]]).

The second component is an abstract class, which is slightly more "heavyweight" than an interface. This is a place where you can specify actual implementation details about the class, so long as they do not depend on the concrete implementation details (e.g., whether the underlying data is stored in an array or a list).

Both of them use generic types for the key and value types, K V.

See code below for more information.

==Code==

Link: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/

===Priority queue interface===

<pre>
/** Priority Queue interface.
*
* This defines the two simplest methods a priority queue can get away with.
*
* This is essentially a barebones list of methods.
*
* Note that Item<K,V> is not defined here, it is defined in your concrete implementation.
*/
public interface PriorityQueue<K,V> extends Iterable<K> {

/** Returns true if the priority queue was changed. */
public boolean insert(k,v);

/** Remove and return the minimum element in this queue. */
public V removeMin() throws Empty;

/** Return, but do not remove, the minimum element in this queue. */
public V peekMin() throws Empty;

/** Returns a key-based iterator. */
public Iterator<K> iterator();

/** Returns an iterable container with all of the Items in this queue. */
public Iterable<Item<K,V>> items();

/** Returns the number of elements in this queue. */
public int size();

/** Returns true if there are no elements in this queue. */
public isEmpty();
}
</pre>

===Abstract class===

<pre>
/** Priority Queue ADT.
*
* Model elements and their priorities as a key-value composite Entry.
*
* The ADT is where we define any constructors or methods
* that are possible to define without knowing the concrete
* implementation of our priority queue.
*/
public abstract class AbstractPriorityQueue<K,V>
implements PriorityQueue<K,V> {

protected static class PQEntry<K,V> implements Entry<K,V> {
private K k;
private V v;
public PQEntry(K key, V value) {
this.k = key; this.v = value;
}

/* Methods associated with the Entry interface: */

/** Return the key associated with this element. */
public K getKey() { return k; }
/** Return the value associated with this element. */
public V getValue() { return v; }

/* Protected utility methods to modify the values (get/set): */

/** Set the key associated with this element. */
protected void setKey(K k) { this.k = k; }

/** Set the value associated with this element. */
protected void setValue(V v) { this.v = v; }

}

}
</pre>