我是一名数据结构类(class)的学生，我目前的任务是制作一个最小优先级队列，我已经完成并测试了它，据我所知它是有效的。我的问题是我们还需要为类(class)计时并分析它们的 Big-O 复杂性；我设计了一个计时类(我为过去的作业做过)，收集数据并绘制它。我的 deleteMin 和 add 方法的复杂度应该为 O(logn)，而 findMin 的复杂度应该为 O(c)，但是我的 add 方法由于某种原因返回了 O(c)。由于我反复测试了 minPQ，我怀疑这个问题与我的计时方式有关，但我很困惑，我希望这里有人能指出我忽略的事情。
顶级域名；我的 add 方法运行速度比应有的快，和/或我测试 add 方法的方法有问题。
编辑:关于计时器如何工作的一些额外信息；基本上它只是向队列中添加随机数以使其大小合适，然后计算再添加一个所需的时间。它从大小 2^startPow 到 2^stopPow，并对每个大小重复计时 iterCount 次并输出平均值。
这是我的队列类:
package assignment11;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.NoSuchElementException;
/**
* Represents a priority queue of generically-typed items.
* The queue is implemented as a min heap.
* The min heap is implemented implicitly as an array.
*
* @author Christopher Nielson
* @uid u0777607
*/
@SuppressWarnings("unchecked")
public class PriorityQueue<AnyType> {
private int currentSize;
private AnyType[] array;
private Comparator<? super AnyType> cmp;
/**
* Constructs an empty priority queue. Orders elements according
* to their natural ordering (i.e., AnyType is expected to be Comparable)
* AnyType is not forced to be Comparable.
*/
public PriorityQueue() {
currentSize = 0;
cmp = null;
array = (AnyType[]) new Object[10]; // safe to ignore warning
}
/**
* Construct an empty priority queue with a specified comparator.
* Orders elements according to the input Comparator (i.e., AnyType need not
* be Comparable).
*/
public PriorityQueue(Comparator<? super AnyType> c) {
currentSize = 0;
cmp = c;
array = (AnyType[]) new Object[10]; // safe to ignore warning
}
/**
* @return the number of items in this priority queue.
*/
public int size() {
return currentSize;
}
/**
* Makes this priority queue empty.
*/
public void clear() {
currentSize = 0;
}
/**
* @return the minimum item in this priority queue.
* @throws NoSuchElementException if this priority queue is empty.
*
* (Runs in constant time.)
*/
public AnyType findMin() throws NoSuchElementException {
if (currentSize == 0) {
throw new NoSuchElementException();
}
return array[0];
}
/**
* Removes and returns the minimum item in this priority queue.
*
* @throws NoSuchElementException if this priority queue is empty.
*
* (Runs in logarithmic time.)
*/
public AnyType deleteMin() throws NoSuchElementException {
if (currentSize == 0) {
throw new NoSuchElementException();
}
AnyType tmp = array[0];
array[0] = array[currentSize - 1];
array[currentSize - 1] = null;
--currentSize;
downHeap(0);
return tmp;
}
/**
* Adds an item to this priority queue.
*
* (Runs in logarithmic time.) Can sometimes terminate early.
*
* @param x -- the item to be inserted
*/
public void add(AnyType x) {
if (currentSize == array.length) {
AnyType[] tmp = array;
array = (AnyType[]) new Object[array.length * 2];
for (int currentIndex = 0; currentIndex < tmp.length; currentIndex++) {
array[currentIndex] = tmp[currentIndex];
}
}
array[currentSize] = x;
++currentSize;
upHeap(currentSize - 1);
}
/**
* Generates a DOT file for visualizing the binary heap.
*/
public void generateDotFile(String filename) {
try(PrintWriter out = new PrintWriter(filename)) {
out.println("digraph Heap {\n\tnode [shape=record]\n");
for(int i = 0; i < currentSize; i++) {
out.println("\tnode" + i + " [label = \"<f0> |<f1> " + array[i] + "|<f2> \"]");
if(((i*2) + 1) < currentSize)
out.println("\tnode" + i + ":f0 -> node" + ((i*2) + 1) + ":f1");
if(((i*2) + 2) < currentSize)
out.println("\tnode" + i + ":f2 -> node" + ((i*2) + 2) + ":f1");
}
out.println("}");
} catch (IOException e) {
System.out.println(e);
}
}
/**
* Internal method for comparing lhs and rhs using Comparator if provided by the
* user at construction time, or Comparable, if no Comparator was provided.
*/
private int compare(AnyType lhs, AnyType rhs) {
if (cmp == null) {
return ((Comparable<? super AnyType>) lhs).compareTo(rhs); // safe to ignore warning
}
// We won't test your code on non-Comparable types if we didn't supply a Comparator
return cmp.compare(lhs, rhs);
}
/**
* Internal method to reheapify upward.
*
* @param root Item where reheapifying will begin
*/
private void upHeap(int root) {
// check if root is less than parent
if (root >= 0 && compare(array[root], array[(root - 1) / 2]) < 0) {
AnyType tmp = array[(root - 1) / 2];
array[(root - 1) / 2] = array[root];
array[root] = tmp;
upHeap((root - 1) / 2);
}
}
/**
* Internal method to reheapify downward.
*
* @param root Item where reheapifying will begin.
*/
private void downHeap(int root) {
// check if left child is less than root
if ((root * 2) + 1 < currentSize && array[(root * 2) + 1] != null && compare(array[(root * 2) + 1], array[root]) < 0) {
// check if right child is less than left child
if ((root * 2) + 2 < currentSize && array[(root * 2) + 2] != null && compare(array[(root * 2) + 2], array[(root * 2) + 1]) < 0) {
// swap with right child
AnyType tmp = array[root];
array[root] = array[(root * 2) + 2];
array[(root * 2) + 2] = tmp;
downHeap((root * 2) + 2);
} else {
// swap with left child
AnyType tmp = array[root];
array[root] = array[(root * 2) + 1];
array[(root * 2) + 1] = tmp;
downHeap((root * 2) + 1);
}
} else if ((root * 2) + 2 < currentSize && array[(root * 2) + 2] != null && compare(array[(root * 2) + 2], array[root]) < 0) {
// swap with right child
AnyType tmp = array[root];
array[root] = array[(root * 2) + 2];
array[(root * 2) + 2] = tmp;
downHeap((root * 2) + 2);
}
}
// LEAVE IN for grading purposes
public Object[] toArray() {
Object[] ret = new Object[currentSize];
for(int i = 0; i < currentSize; i++) {
ret[i] = array[i];
}
return ret;
}
}
这是我的计时课:
package assignment11;
import java.io.File;
import java.io.FileOutputStream;
import java.io.OutputStreamWriter;
import java.util.Random;
/**
* @author Christopher Nielson
* @uid u0777607
*/
public class PriorityQueueTimer {
private static int startPow = 10;
private static int stopPow = 24;
private static int iterCount = 10000;
private static Random rand;
private static OutputStreamWriter fileOut;
public static void main(String[] args) {
timeAdd();
// timeDeleteMin();
// timeFindMin();
System.out.println("Finished timing!");
}
/**
* Times add method of PriorityQueue for different data sizes and outputs results to a file.
*/
private static void timeAdd() {
try {
fileOut = new OutputStreamWriter(new FileOutputStream(new File("assignment11-addTimer.csv")));
PriorityQueue<Integer> addTimer;
for (int currentPow = startPow; currentPow <= stopPow; currentPow++) {
int dataSize = (int) Math.pow(2, currentPow);
System.out.print("Timing add on datasize " + dataSize + " (Power: " + currentPow + ")...");
long totalTime = 0;
long stopTime;
addTimer = new PriorityQueue<Integer>();
rand = new Random(13);
for (int currentRand = 0; currentRand < dataSize; currentRand++) {
addTimer.add(rand.nextInt());
}
long startTime = System.nanoTime();
while (System.nanoTime() - startTime < 1000000){}
for (int currentIter = 0; currentIter < iterCount; currentIter++) {
startTime = System.nanoTime();
addTimer.add(rand.nextInt());
stopTime = System.nanoTime();
addTimer.deleteMin();
totalTime += stopTime - startTime;
}
System.out.println("Finished!");
fileOut.write(dataSize + "\t" + (totalTime / iterCount) + "\n");
fileOut.flush();
}
fileOut.close();
} catch(Exception e) {
System.err.println(e.getMessage());
e.printStackTrace();
}
}
/**
* Times deleteMin method of PriorityQueue for different data sizes and outputs results to a file.
*/
private static void timeDeleteMin() {
try {
fileOut = new OutputStreamWriter(new FileOutputStream(new File("assignment11-deleteMinTimer.csv")));
PriorityQueue<Integer> deleteTimer;
for (int currentPow = startPow; currentPow <= stopPow; currentPow++) {
int dataSize = (int) Math.pow(2, currentPow);
System.out.print("Timing deleteMin on datasize " + dataSize + " (Power: " + currentPow + ")...");
long totalTime = 0;
long stopTime;
deleteTimer = new PriorityQueue<Integer>();
rand = new Random(13);
for (int currentRand = 0; currentRand < dataSize; currentRand++) {
deleteTimer.add(rand.nextInt());
}
long startTime = System.nanoTime();
while (System.nanoTime() - startTime < 1000000){}
for (int currentIter = 0; currentIter < iterCount; currentIter++) {
startTime = System.nanoTime();
deleteTimer.deleteMin();
stopTime = System.nanoTime();
deleteTimer.add(rand.nextInt());
totalTime += stopTime - startTime;
}
System.out.println("Finished!");
fileOut.write(dataSize + "\t" + (totalTime / iterCount) + "\n");
fileOut.flush();
}
fileOut.close();
} catch(Exception e) {
System.err.println(e.getMessage());
e.printStackTrace();
}
}
/**
* Times findMin method of PriorityQueue for different data sizes and outputs results to a file.
*/
private static void timeFindMin() {
try {
fileOut = new OutputStreamWriter(new FileOutputStream(new File("assignment11-findMinTimer.csv")));
PriorityQueue<Integer> findTimer;
for (int currentPow = startPow; currentPow <= stopPow; currentPow++) {
findTimer = new PriorityQueue<Integer>();
int dataSize = (int) Math.pow(2, currentPow);
System.out.print("Timing findMin on datasize " + dataSize + " (Power: " + currentPow + ")...");
long totalTime = 0;
long stopTime;
rand = new Random(13);
for (int currentRand = 0; currentRand < dataSize; currentRand++) {
findTimer.add(rand.nextInt());
}
long startTime = System.nanoTime();
while (System.nanoTime() - startTime < 1000000){}
for (int currentIter = 0; currentIter < iterCount; currentIter++) {
startTime = System.nanoTime();
findTimer.findMin();
stopTime = System.nanoTime();
totalTime += stopTime - startTime;
}
System.out.println("Finished!");
fileOut.write(dataSize + "\t" + (totalTime / iterCount) + "\n");
fileOut.flush();
}
fileOut.close();
} catch(Exception e) {
System.err.println(e.getMessage());
e.printStackTrace();
}
}
}
这是我目前的图表结果: Timing Results
提前致谢!
最佳答案
这是一个简单的论证，其效果是插入是 O(1) 平均(当然是 O(log n) 最坏情况)。
通过将最小元素分配为根，将剩余元素划分为随机子集，并在每个子集上构造子树作为根的 child ，在随机元素集上构造随机二叉堆。 (通过随机插入构建的堆的实际分布可能与此不同，但我猜不是实质性的。)
我们向这个堆中插入一个随机元素x。扩展数组是 O(1) 摊销的，因此主要成本是堆上成本，它与置换的元素数量成正比。让我们计算一个期望值。
鉴于堆有n个现有元素，新元素小于根的概率为1/(n+1)，导致至多log (n+1) 置换元素。否则，位移被限制在 (n-1)/2 元素的子树之一。 x 和该子树的元素都以大于根为条件，因此我们可以归纳推理发现预期成本是
log (n+1)
T(n) = --------- + T((n - 1)/2)
n + 1
T(0) = 0,
因此我们发现，对于 n = 2^k - 1，
T(2^k - 1) = k/2^k + T(2^(k-1) - 1)
= sum_{j=0}^k j/2^j
= O(1) by standard analysis techniques.
(所有对数都以 2 为底。)
关于java - 最小优先级队列的复杂性问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40638461/