(The entire project is here.)
Intro
I have this priority queue data structure for non-negative integer priority keys. I recall that it is called Dial's heap.
Code
Implementation
com.github.coderodde.util.IntegerMinimumPriorityQueue.java:
package com.github.coderodde.util;
/**
* This interface defines the API for minimum priority queues with integer
* priority keys.
*
* @param <D> the data type of the satellite datums.
*
* @version 1.0.0 (May 10, 2024)
* @since 1.0.0 (May 10, 2024)
*/
public interface IntegerMinimumPriorityQueue<D> extends Iterable<D>, Cloneable {
/**
* Inserts a new datum {@code datum} to this heap with the given priority
* {@code priority}.
*
* @param datum the datum to insert.
* @param priority the priority key to set.
*/
public void insert(final D datum, final int priority);
/**
* Updates the priority of the satellite datum {@code datum} to
* {@code priority}. This method can handle both increasing and decreasing
* of the priority key.
*
* @param datum the datum of which priority to update.
* @param priority the new priority of {@code datum}.
*/
public void updatePriority(final D datum, final int priority);
/**
* Returns the minimal priority throughout the contents of this heap. If
* this heap is empty, {@code -1} is returned.
*
* @return the minimal priority.
*/
public int minimumPriority();
/**
* Returns the datum with the lowest priority key, or {@code null} if this
* heap is empty.
*
* @return the datum with the lowest priority key, or {@code null} if this
* heap is empty.
*/
public D minimumNode();
/**
* Returns {@code true} if the {@code datum} is stored in this heap.
*
* @param datum the query datum.
*
* @return {@code true} if the {@code datum} is stored in this heap.
*/
public boolean containsDatum(final D datum);
/**
* Returns the current priority of the input datum.
*
* @param datum the datum to query.
* @return the current priority of {@code datum}.
*/
public int getPriority(final D datum);
/**
* Removes and returns the datum with the lowest priority key, or
* {@code null} if this heap is empty.
*
* @return the datum with the lowest priority key, or {@code null} if this
* heap is empty.
*/
public D extractMinimum();
/**
* Removes the datum {@code datum} from this heap.
*
* @param datum to remove.
*/
public void remove(final D datum);
/**
* Clears all the data from this heap.
*/
public void clear();
/**
* Since the heap cannot contract the collision chain table, the remedy to
* do that is to clone it which will return another heap with the same
* content, but with the table as small as is necessary to accommodate also
* the maximum priority nodes.
*
* @return the clone of this heap.
*/
public Object clone();
/**
* Returns the number of datums stored in this heap.
*
* @return the number of datums stored in this heap.
*/
public int size();
}
com.github.coderodde.util.DialsHeap.java:
package com.github.coderodde.util;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
/**
* This class implements a priority queue data structure called a Dial's heap.
*
* @param <D> the type of the satellite data.
*
* @version 1.0.1 (May 12, 2024)
* @since 1.0.0 (May 10, 2024)
*/
public class DialsHeap<D> implements IntegerMinimumPriorityQueue<D> {
/**
* This static inner class implements the node type for this heap.
*
* @param <D> the satellite data type.
*/
private static final class DialsHeapNode<D> {
/**
* The actual satellite datum.
*/
final D datum;
/**
* The priority key of this node. Must be at least zero (0).
*/
int priority;
/**
* The previous node in the collision chain or {@code null} if this node
* is the head of the collision chain.
*/
DialsHeapNode<D> prev;
/**
* The next node in the collision chain or {@code null} if this node is
* the tail of the collision chain.
*/
DialsHeapNode<D> next;
/**
* Constructs a new heap node.'
*
* @param datum the satellite datum.
* @param priority the priority key.
*/
DialsHeapNode(final D datum, final int priority) {
this.datum = datum;
this.priority = priority;
}
}
/**
* This inner class implements the iterator over all satellite data in this
* heap in the ascending priority key order.
*/
private final class DialsHeapIterator implements Iterator<D> {
/**
* Caches the number of nodes already iterated.
*/
private int iterated = 0;
/**
* The current heap node.
*/
private DialsHeapNode<D> currentDialsHeapNode;
/**
* Constructs a new iterator over the enclosing heap.
*/
private DialsHeapIterator() {
// Attempt to find the head node:
for (final DialsHeapNode<D> headNode : table) {
if (headNode != null) {
currentDialsHeapNode = headNode;
return;
}
}
// Once here, the heap is empty, return null:
currentDialsHeapNode = null;
}
/**
* {@inheritDoc }
*/
@Override
public boolean hasNext() {
return iterated < nodeMap.size();
}
/**
* {@inheritDoc}
*/
@Override
public D next() {
if (!hasNext()) {
throw new NoSuchElementException("Nothing to iterate left.");
}
final D returnElement = currentDialsHeapNode.datum;
iterated++;
currentDialsHeapNode = computeNextDialsHeapNode();
return returnElement;
}
/**
* Returns the next heap node.
*
* @return the next heap node in the iteration order.
*/
private DialsHeapNode<D> computeNextDialsHeapNode() {
if (iterated == nodeMap.size()) {
// Once here, iteration is complete.
return null;
}
if (currentDialsHeapNode.next != null) {
// currentDialsHeapNode has minimum priority key, move to its
// right sibling/neighbor in the collision chain:
return currentDialsHeapNode.next;
}
// Search the next smallest priority node:
for (int p = currentDialsHeapNode.priority + 1;
p < table.length;
p++) {
if (table[p] != null) {
// Found!
return table[p];
}
}
// We should never ever get here.
throw new IllegalStateException("Should not get here.");
}
}
/**
* The default table capacity.
*/
private static final int DEFAULT_TABLE_CAPACITY = 8;
/**
* The table mapping each slot to the head of a collision chain.
*/
private DialsHeapNode<D>[] table;
/**
* The map mapping the satellite datums to their respective heap nodes.
*/
private final Map<D, DialsHeapNode<D>> nodeMap = new HashMap<>();
/**
* Constructs a heap with {@code tableCapacity} as the capacity of the
* internal collision chain table.
*
* @param tableCapacity the requested collision chain capacity.
*/
public DialsHeap(final int tableCapacity) {
this.table = new DialsHeapNode[tableCapacity];
}
/**
* Constructs a heap0 with default collision chain table capacity.
*/
public DialsHeap() {
this(DEFAULT_TABLE_CAPACITY);
}
/**
* {@inheritDoc }
*/
@Override
public Iterator<D> iterator() {
return new DialsHeapIterator();
}
/**
* {@inheritDoc}
*/
@Override
public void insert(final D datum, final int priority) {
if (nodeMap.containsKey(datum)) {
// Once here, the input datum is already in this heap. Use
// updatePriority for adjusting the priority key.
return;
}
checkPriority(priority);
if (mustExpand(priority)) {
expand(priority);
}
final DialsHeapNode<D> node = new DialsHeapNode<>(datum, priority);
nodeMap.put(datum, node);
linkImpl(node, priority);
}
/**
* {@inheritDoc}
*/
@Override
public void updatePriority(final D datum, final int priority) {
if (mustExpand(priority)) {
expand(priority);
}
final DialsHeapNode<D> node = nodeMap.get(datum);
unlinkImpl(node);
linkImpl(node, priority);
node.priority = priority;
}
/**
* {@inheritDoc}
*/
@Override
public int minimumPriority() {
return accessMinimumPriorityNode().priority;
}
/**
* {@inheritDoc}
*/
@Override
public D minimumNode() {
if (nodeMap.isEmpty()) {
return null;
}
return accessMinimumPriorityNode().datum;
}
/**
* {@inheritDoc}
*/
@Override
public boolean containsDatum(final D datum) {
return nodeMap.containsKey(datum);
}
/**
* {@inheritDoc}
*/
@Override
public int getPriority(final D datum) {
return nodeMap.get(datum).priority;
}
/**
* {@inheritDoc}
*/
@Override
public D extractMinimum() {
if (nodeMap.isEmpty()) {
return null;
}
final DialsHeapNode<D> node = accessMinimumPriorityNode();
unlinkImpl(node);
nodeMap.remove(node.datum);
return node.datum;
}
/**
* {@inheritDoc}
*/
@Override
public void remove(final D datum) {
unlinkImpl(nodeMap.get(datum));
nodeMap.remove(datum);
}
/**
* {@inheritDoc}
*/
@Override
public void clear() {
nodeMap.clear();
Arrays.fill(table, null);
}
/**
* {@inheritDoc}
*/
@Override
public Object clone() {
final int maximumPriorityKey = getMaximumPriority();
final int cloneCapacity = getNextCapacity(maximumPriorityKey);
final DialsHeap<D> copy = new DialsHeap<>(cloneCapacity);
for (final Map.Entry<D, DialsHeapNode<D>> entry : nodeMap.entrySet()) {
copy.insert(entry.getValue().datum, entry.getValue().priority);
}
return copy;
}
/**
* {@inheritDoc}
*/
@Override
public int size() {
return nodeMap.size();
}
/**
* {@inheritDoc }
*/
@Override
public boolean isEmpty() {
return nodeMap.isEmpty();
}
/**
* Returns the head of the collision chain with the lowest priority key.
*
* @return the head of the collision chain with the lowest priority key.
*/
private DialsHeapNode<D> accessMinimumPriorityNode() {
for (int p = 0; p != table.length; p++) {
if (table[p] != null) {
return table[p];
}
}
throw new IllegalStateException("Should not get here.");
}
/**
* Links the node {@code node} to the head of the collision chain with
* priority key {@code priority}.
*
* @param node the node to link.
* @param priority the priority key to link with.
*/
private void linkImpl(final DialsHeapNode<D> node, final int priority) {
final DialsHeapNode<D> currentBucketHead = table[priority];
if (currentBucketHead != null) {
node.next = currentBucketHead;
currentBucketHead.prev = node;
}
table[priority] = node;
}
/**
* Unlinks the node {@code node} from this heap.
*
* @param node the node to unlink.
*/
private void unlinkImpl(final DialsHeapNode<D> node) {
if (node.prev != null) {
node.prev.next = node.next;
if (node.next != null) {
node.next.prev = node.prev;
node.next = null;
}
node.prev = null;
} else {
// Once here, node.prev == null!
if (node.next != null) {
node.next.prev = null;
table[node.priority] = node.next;
node.next = null;
} else {
// Remove the last node in the collision chain:
table[node.priority] = null;
}
}
}
/**
* Returns {@code true} if this heap's table cannot accommodate a node with
* priority {@code priority}.
*
* @param priority the priority to query.
*
* @return {@code true} if the table must be expanded.
*/
private boolean mustExpand(final int priority) {
return priority >= table.length;
}
/**
* Expands the internal table {@code table} such that it can accommodate the
* priority key {@code priority}, while being smallest such table.
*
* @param priority the requested priority key.
*/
private void expand(final int priority) {
final int nextCapacity = getNextCapacity(priority);
this.table = Arrays.copyOf(table, nextCapacity);
}
/**
* Returns the capacity that is sufficiently large in order to accommodate
* the heap nodes with priority {@code priority}.
*
* @param priority the requested priority.
*
* @return the next capacity to expand with.
*/
private int getNextCapacity(final int priority) {
int nextCapacity = table.length;
while (nextCapacity <= priority) {
nextCapacity *= 2;
}
return nextCapacity;
}
/**
* Returns the maximum priority key in this heap.
*
* @return the maximum priority key in this heap.
*/
private int getMaximumPriority() {
for (int priority = table.length - 1; priority >= 0; priority--) {
if (table[priority] != null) {
return priority;
}
}
return -1;
}
/**
* Makes sure that the input priority is non-negative.
*
* @param priority the priority to check.
*
* @throws IllegalArgumentException if the input priority is negative.
*/
private void checkPriority(final int priority) {
if (priority < 0) {
throw new IllegalArgumentException(
String.format(
"The input priority is negtive (%d).\n",
priority));
}
}
}
com.github.coderodde.util.CachedDialsHeap.java:
package com.github.coderodde.util;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
/**
* This class implements a priority queue data structure called a Dial's heap.
*
* @param <D> the type of the satellite data.
*
* @version 1.0.0 (May 10, 2024)
* @since 1.0.0
*/
public class CachedDialsHeap<D> implements IntegerMinimumPriorityQueue<D> {
/**
* This static inner class implements the node type for this heap.
*
* @param <D> the satellite data type.
*/
private static final class CachedDialsHeapNode<D> {
/**
* The actual satellite datum.
*/
final D datum;
/**
* The priority key of this node. Must be at least zero (0).
*/
int priority;
/**
* The previous node in the collision chain or {@code null} if this node
* is the head of the collision chain.
*/
CachedDialsHeapNode<D> prev;
/**
* The next node in the collision chain or {@code null} if this node is
* the tail of the collision chain.
*/
CachedDialsHeapNode<D> next;
/**
* Constructs a new heap node.'
*
* @param datum the satellite datum.
* @param priority the priority key.
*/
CachedDialsHeapNode(final D datum, final int priority) {
this.datum = datum;
this.priority = priority;
}
}
/**
* This inner class implements the iterator over all satellite data in this
* heap in the ascending priority key order.
*/
private final class CachedDialsHeapIterator implements Iterator<D> {
/**
* Caches the number of nodes already iterated.
*/
private int iterated = 0;
/**
* The current heap node.
*/
private CachedDialsHeapNode<D> currentDialsHeapNode;
/**
* Constructs a new iterator over the enclosing heap.
*/
private CachedDialsHeapIterator() {
// Attempt to find the head node:
for (final CachedDialsHeapNode<D> headNode : table) {
if (headNode != null) {
currentDialsHeapNode = headNode;
return;
}
}
// Once here, the heap is empty, return null:
currentDialsHeapNode = null;
}
/**
* {@inheritDoc }
*/
@Override
public boolean hasNext() {
return iterated < nodeMap.size();
}
/**
* {@inheritDoc}
*/
@Override
public D next() {
if (!hasNext()) {
throw new NoSuchElementException("Nothing to iterate left.");
}
final D returnElement = currentDialsHeapNode.datum;
iterated++;
currentDialsHeapNode = computeNextDialsHeapNode();
return returnElement;
}
/**
* Returns the next heap node.
*
* @return the next heap node in the iteration order.
*/
private CachedDialsHeapNode<D> computeNextDialsHeapNode() {
if (iterated == nodeMap.size()) {
// Once here, iteration is complete.
return null;
}
if (currentDialsHeapNode.next != null) {
// currentDialsHeapNode has minimum priority key, move to its
// right sibling/neighbor in the collision chain:
return currentDialsHeapNode.next;
}
// Search the next smallest priority node:
for (int p = currentDialsHeapNode.priority + 1;
p < table.length;
p++) {
if (table[p] != null) {
// Found!
return table[p];
}
}
// We should never ever get here.
throw new IllegalStateException("Should not get here.");
}
}
/**
* The default table capacity.
*/
private static final int DEFAULT_TABLE_CAPACITY = 8;
/**
* The table mapping each slot to the head of a collision chain.
*/
private CachedDialsHeapNode<D>[] table;
/**
* The map mapping the satellite datums to their respective heap nodes.
*/
private final Map<D, CachedDialsHeapNode<D>> nodeMap = new HashMap<>();
/**
* Caches the minimum priority so that {@link #extractMinimum()} and
* {@link #minimumNode()} and {@link #minimumPriority()} run in constant
* time.
*/
private int minimumPriority = Integer.MAX_VALUE;
/**
* Constructs a heap with {@code tableCapacity} as the capacity of the
* internal collision chain table.
*
* @param tableCapacity the requested collision chain capacity.
*/
public CachedDialsHeap(final int tableCapacity) {
this.table = new CachedDialsHeapNode[tableCapacity];
}
/**
* Constructs a heap0 with default collision chain table capacity.
*/
public CachedDialsHeap() {
this(DEFAULT_TABLE_CAPACITY);
}
/**
* {@inheritDoc }
*/
@Override
public Iterator<D> iterator() {
return new CachedDialsHeapIterator();
}
/**
* {@inheritDoc}
*/
@Override
public void insert(final D datum, final int priority) {
if (nodeMap.containsKey(datum)) {
// Once here, the input datum is already in this heap. Use
// updatePriority for adjusting the priority key.
return;
}
checkPriority(priority);
minimumPriority = Math.min(minimumPriority, priority);
if (mustExpand(priority)) {
expand(priority);
}
final CachedDialsHeapNode<D> node =
new CachedDialsHeapNode<>(
datum,
priority);
nodeMap.put(datum, node);
linkImpl(node, priority);
}
/**
* {@inheritDoc}
*/
@Override
public void updatePriority(final D datum, final int priority) {
checkPriority(priority);
minimumPriority = Math.min(minimumPriority, priority);
if (mustExpand(priority)) {
expand(priority);
}
final CachedDialsHeapNode<D> node = nodeMap.get(datum);
unlinkImpl(node);
linkImpl(node, priority);
node.priority = priority;
}
/**
* {@inheritDoc}
*/
@Override
public int minimumPriority() {
return minimumPriority;
}
/**
* {@inheritDoc}
*/
@Override
public D minimumNode() {
if (nodeMap.isEmpty()) {
return null;
}
return table[minimumPriority].datum;
}
/**
* {@inheritDoc}
*/
@Override
public boolean containsDatum(final D datum) {
return nodeMap.containsKey(datum);
}
/**
* {@inheritDoc}
*/
@Override
public int getPriority(final D datum) {
return nodeMap.get(datum).priority;
}
/**
* {@inheritDoc}
*/
@Override
public D extractMinimum() {
if (nodeMap.isEmpty()) {
return null;
}
final CachedDialsHeapNode<D> node = accessMinimumPriorityNode();
unlinkImpl(node);
nodeMap.remove(node.datum);
if (table[minimumPriority] == null) {
updateMinimumPriority();
}
return node.datum;
}
/**
* {@inheritDoc}
*/
@Override
public void remove(final D datum) {
final CachedDialsHeapNode<D> node = nodeMap.get(datum);
unlinkImpl(node);
nodeMap.remove(datum);
if (table[node.priority] == null) {
updateMinimumPriority();
}
}
/**
* {@inheritDoc}
*/
@Override
public void clear() {
minimumPriority = Integer.MAX_VALUE;
nodeMap.clear();
Arrays.fill(table, null);
}
/**
* {@inheritDoc}
*/
@Override
public Object clone() {
final int maximumPriorityKey = getMaximumPriority();
final int cloneCapacity = getNextCapacity(maximumPriorityKey);
final CachedDialsHeap<D> copy = new CachedDialsHeap<>(cloneCapacity);
for (final Map.Entry<D, CachedDialsHeapNode<D>> entry : nodeMap.entrySet()) {
copy.insert(entry.getValue().datum, entry.getValue().priority);
}
return copy;
}
/**
* {@inheritDoc}
*/
@Override
public int size() {
return nodeMap.size();
}
/**
* {@inheritDoc }
*/
@Override
public boolean isEmpty() {
return nodeMap.isEmpty();
}
/**
* Returns the head of the collision chain with the lowest priority key.
*
* @return the head of the collision chain with the lowest priority key.
*/
private CachedDialsHeapNode<D> accessMinimumPriorityNode() {
for (int p = 0; p != table.length; p++) {
if (table[p] != null) {
return table[p];
}
}
throw new IllegalStateException("Should not get here.");
}
/**
* Links the node {@code node} to the head of the collision chain with
* priority key {@code priority}.
*
* @param node the node to link.
* @param priority the priority key to link with.
*/
private void linkImpl(final CachedDialsHeapNode<D> node, final int priority) {
final CachedDialsHeapNode<D> currentBucketHead = table[priority];
if (currentBucketHead != null) {
node.next = currentBucketHead;
currentBucketHead.prev = node;
}
table[priority] = node;
}
/**
* Unlinks the node {@code node} from this heap.
*
* @param node the node to unlink.
*/
private void unlinkImpl(final CachedDialsHeapNode<D> node) {
if (node.prev != null) {
node.prev.next = node.next;
if (node.next != null) {
node.next.prev = node.prev;
node.next = null;
}
node.prev = null;
} else {
// Once here, node.prev == null!
if (node.next != null) {
node.next.prev = null;
table[node.priority] = node.next;
node.next = null;
} else {
// Remove the last node in the collision chain:
table[node.priority] = null;
}
}
}
/**
* Returns {@code true} if this heap's table cannot accommodate a node with
* priority {@code priority}.
*
* @param priority the priority to query.
*
* @return {@code true} if the table must be expanded.
*/
private boolean mustExpand(final int priority) {
return priority >= table.length;
}
/**
* Expands the internal table {@code table} such that it can accommodate the
* priority key {@code priority}, while being smallest such table.
*
* @param priority the requested priority key.
*/
private void expand(final int priority) {
final int nextCapacity = getNextCapacity(priority);
this.table = Arrays.copyOf(table, nextCapacity);
}
/**
* Returns the capacity that is sufficiently large in order to accommodate
* the heap nodes with priority {@code priority}.
*
* @param priority the requested priority.
*
* @return the next capacity to expand with.
*/
private int getNextCapacity(final int priority) {
int nextCapacity = table.length;
while (nextCapacity <= priority) {
nextCapacity *= 2;
}
return nextCapacity;
}
/**
* Returns the maximum priority key in this heap.
*
* @return the maximum priority key in this heap.
*/
private int getMaximumPriority() {
for (int priority = table.length - 1; priority >= 0; priority--) {
if (table[priority] != null) {
return priority;
}
}
return -1;
}
/**
* Makes sure that the input priority is non-negative.
*
* @param priority the priority to check.
*
* @throws IllegalArgumentException if the input priority is negative.
*/
private void checkPriority(final int priority) {
if (priority < 0) {
throw new IllegalArgumentException(
String.format(
"The input priority is negtive (%d).\n",
priority));
}
}
/**
* Updates the minimum priority.
*/
private void updateMinimumPriority() {
for (int p = minimumPriority + 1; p < table.length; p++) {
if (table[p] != null) {
minimumPriority = p;
return;
}
}
minimumPriority = -1;
}
}
Benchmark
com.github.coderodde.util.benchmark.Benchmark.java:
package com.github.coderodde.util.benchmark;
import com.github.coderodde.util.CachedDialsHeap;
import com.github.coderodde.util.DialsHeap;
import com.github.coderodde.util.IntegerMinimumPriorityQueue;
import java.util.Arrays;
import java.util.Random;
/**
* This class implements the benchmark program for the priority queues.
*
* @version 1.0.1 (May 12, 2024)
* @since 1.0.0 (May 11, 2024)
*/
public final class Benchmark {
/**
* The upper bound value for the randomly generated integers.
*/
private static final int UPPER_BOUND = 150_000;
/**
* The benchmarking array lengths.
*/
private static final int ARRAY_LENGTH = 1_000_000;
/**
* The entry point of the benchmark.
*
* @param args the command line arguments.
*/
public static void main(String[] args) {
final long seed = System.currentTimeMillis();
System.out.printf("seed = %d.\n", seed);
warmup(seed);
benchmark(seed);
}
/**
* Warms up the benchmark.
*
* @param seed the random number generator seed.
*/
private static void warmup(final long seed) {
runBenchmark(
new DialsHeap<>(),
seed,
false);
runBenchmark(
new CachedDialsHeap<>(),
seed,
false);
}
/**
* Benchmarks the heaps.
*
* @param seed the random number generator seed.
*/
private static void benchmark(final long seed) {
final Integer[] output1 =
runBenchmark(
new DialsHeap<>(),
seed,
true);
System.out.println();
final Integer[] output2 =
runBenchmark(
new CachedDialsHeap<>(),
seed,
true);
System.out.println();
System.out.printf(
"Heaps agree: %b.\n",
Arrays.equals(output1,
output2));
}
/**
* Implements the benchmark/warmup runner.
*
* @param heap the heap to benchmark.
* @param seed the random number generator seed.
* @param print the flag specifying whether to print the intermediate
* results.
*
* @return the processed data.
*/
private static Integer[] runBenchmark(
final IntegerMinimumPriorityQueue<Integer> heap,
final long seed,
final boolean print) {
final Random random = new Random(seed);
final Integer[] array =
getRandomIntegerArray(
random,
ARRAY_LENGTH,
UPPER_BOUND);
long totalDuration = 0L;
long start = System.currentTimeMillis();
for (final Integer i : array) {
heap.insert(i, i);
}
long end = System.currentTimeMillis();
totalDuration += end - start;
if (print) {
System.out.printf("insert() in %d milliseconds.\n", end - start);
}
final int[] priorities =
getRandomIntArray(
random,
ARRAY_LENGTH,
UPPER_BOUND);
start = System.currentTimeMillis();
for (int i = 0; i < heap.size(); i++) {
heap.updatePriority(array[i], priorities[i]);
}
end = System.currentTimeMillis();
totalDuration += end - start;
if (print) {
System.out.printf(
"updatePriority() in %d milliseconds.\n",
end - start);
}
final Integer[] output = new Integer[heap.size()];
int index = 0;
start = System.currentTimeMillis();
while (heap.size() != 0) {
output[index++] = heap.extractMinimum();
}
end = System.currentTimeMillis();
totalDuration += end - start;
if (print) {
System.out.printf(
"extractMinimum() in %d milliseconds.\n",
end - start);
System.out.printf(
"Total duration of %s: %d milliseconds.\n",
heap.getClass().getSimpleName(),
totalDuration);
}
return output;
}
/**
* Returns the random array of {@code Integer}s. Each integer is drawn from
* the range {@code [0, upperBound - 1]}.
*
* @param random the random number generator.
* @param length the length of the generated array.
* @param upperBound the upper bound of the integer values.
*
* @return the random integer array.
*/
private static Integer[]
getRandomIntegerArray(
final Random random,
final int length,
final int upperBound) {
final Integer[] array = new Integer[length];
for (int i = 0; i < length; i++) {
array[i] = random.nextInt(upperBound);
}
return array;
}
/**
* Returns the random array of {@code int}s. Each integer is drawn from
* the range {@code [0, upperBound - 1]}.
*
* @param random the random number generator.
* @param length the length of the generated array.
* @param upperBound the upper bound of the integer values.
*
* @return the random integer array.
*/
private static int[]
getRandomIntArray(
final Random random,
final int length,
final int upperBound) {
final int[] array = new int[length];
for (int i = 0; i < length; i++) {
array[i] = random.nextInt(upperBound);
}
return array;
}
}
Unit testing
com.github.coderodde.util.AbstractDialsHeapTest.java:
package com.github.coderodde.util;
import java.util.Iterator;
import java.util.NoSuchElementException;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import org.junit.Before;
import org.junit.Test;
public abstract class AbstractDialsHeapTest {
protected IntegerMinimumPriorityQueue<String> heap;
private Iterator<String> iterator;
public AbstractDialsHeapTest(
final IntegerMinimumPriorityQueue<String> heap) {
this.heap = heap;
}
@Before
public void before() {
heap = new DialsHeap<String>();
iterator = null;
}
@Test
public void testIterator() {
iterator = heap.iterator();
assertFalse(iterator.hasNext());
try {
iterator.next();
fail("Should throw on empty iterator.");
} catch (final NoSuchElementException ex) {
}
heap.insert("A1", 1);
heap.insert("A2", 1);
heap.insert("A3", 1);
heap.insert("C1", 3);
heap.insert("B1", 2);
heap.insert("B2", 2);
iterator = heap.iterator();
assertEquals("A3", iterator.next());
assertEquals("A2", iterator.next());
assertEquals("A1", iterator.next());
assertEquals("B2", iterator.next());
assertEquals("B1", iterator.next());
assertEquals("C1", iterator.next());
assertFalse(iterator.hasNext());
}
@Test
public void testInsert() {
heap.insert("A", 1);
heap.insert("C", 3);
heap.insert("B", 2);
assertEquals("A", heap.minimumNode());
assertEquals(1, heap.minimumPriority());
assertEquals("A", heap.extractMinimum());
assertEquals("B", heap.minimumNode());
assertEquals(2, heap.minimumPriority());
assertEquals("B", heap.extractMinimum());
assertEquals("C", heap.minimumNode());
assertEquals(3, heap.minimumPriority());
assertEquals("C", heap.extractMinimum());
assertEquals(0, heap.size());
}
@Test
public void testUpdatePriority() {
heap.insert("B", 2);
heap.insert("A", 3);
heap.insert("C", 1);
heap.updatePriority("A", 1);
heap.updatePriority("B", 2);
heap.updatePriority("C", 3);
assertEquals("A", heap.extractMinimum());
assertEquals("B", heap.extractMinimum());
assertEquals("C", heap.extractMinimum());
}
@Test
public void testMinimumPriority() {
heap.insert("A", 1);
heap.insert("B", 2);
heap.insert("C", 3);
assertEquals(1, heap.minimumPriority());
assertEquals("A", heap.extractMinimum());
assertEquals(2, heap.minimumPriority());
assertEquals("B", heap.extractMinimum());
assertEquals(3, heap.minimumPriority());
assertEquals("C", heap.extractMinimum());
}
@Test
public void testMinimumNode() {
heap.insert("A", 1);
heap.insert("B", 2);
heap.insert("C", 3);
assertEquals("A", heap.minimumNode());
assertEquals("A", heap.extractMinimum());
assertEquals("B", heap.minimumNode());
assertEquals("B", heap.extractMinimum());
assertEquals("C", heap.minimumNode());
assertEquals("C", heap.extractMinimum());
}
@Test
public void testGetPriority() {
heap.insert("X", 10);
assertEquals(10, heap.getPriority("X"));
heap.updatePriority("X", 9);
assertEquals(9, heap.getPriority("X"));
heap.updatePriority("X", 26);
assertEquals(26, heap.getPriority("X"));
}
@Test
public void testExtractMinimum() {
for (int i = 10; i >= 0; i--) {
heap.insert(Integer.toString(i), i);
}
for (int i = 0; i <= 10; i++) {
assertEquals(Integer.toString(i), heap.extractMinimum());
}
}
@Test
public void testRemove() {
for (int i = 10; i >= 0; i--) {
heap.insert(Integer.toString(i), i);
}
// Remove odd numbers:
for (int i = 1; i <= 10; i += 2) {
heap.remove(Integer.toString(i));
}
// Make sure all the even numbers are still in the heap:
for (int i = 0; i <= 10; i += 2) {
heap.containsDatum(Integer.toString(i));
}
}
@Test
public void testClone() {
for (int i = 2; i < 10; i++) {
heap.insert(Integer.toString(i), i);
}
final DialsHeap<String> copy = (DialsHeap<String>) heap.clone();
assertEquals(heap.size(), copy.size());
for (int i = 2; i < 10; i++) {
assertTrue(copy.containsDatum(Integer.toString(i)));
}
}
@Test
public void testSize() {
for (int i = 0; i < 10; i++) {
assertEquals(i, heap.size());
heap.insert(Integer.toString(i), i);
assertEquals(i + 1, heap.size());
}
}
@Test
public void testCanExpand() {
heap.insert("A", 1000);
}
}
com.github.coderodde.util.DialsHeapTest.java:
package com.github.coderodde.util;
public final class DialsHeapTest extends AbstractDialsHeapTest {
public DialsHeapTest() {
super(new DialsHeap<>());
}
}
com.github.coderodde.util.CachedDialsHeapTest.java:
package com.github.coderodde.util;
public final class CachedDialsHeapTest extends AbstractDialsHeapTest {
public CachedDialsHeapTest() {
super(new CachedDialsHeap<>());
}
}
Typical benchmark output
The typical benchmark output is:
seed = 1715856367754.
insert() in 126 milliseconds.
updatePriority() in 22 milliseconds.
extractMinimum() in 4424 milliseconds.
Total duration of DialsHeap: 4572 milliseconds.
insert() in 195 milliseconds.
updatePriority() in 48 milliseconds.
extractMinimum() in 5620 milliseconds.
Total duration of CachedDialsHeap: 5863 milliseconds.
Heaps agree: true.
Critique request
As always, I would like to receive any commentary on my work.
