使用最小优先级队列的复杂性问题

Question

我是数据结构类的学生，目前的任务是创建一个最小优先级队列，我已经完成并测试了，并且据我所知，它可以工作。我的问题是，我们还需要安排我们的课程并分析他们的Big-O复杂性;我设计了一个授课班（我为过去的任务完成），收集数据并绘制它。我的deleteMin和add方法的复杂度应该是O（logn），而findMin应该有O（c），但是我的add方法由于某种原因返回O（c）。由于我已经重复测试了minPQ，我怀疑这个问题与我的计时方式有关，但我很难过，希望有人能够接受我忽略的一些东西。

TLD;我的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

提前感谢！

Answer 1

下面是插入为O(1)平均值（当然是O(log n)最坏的情况）的效果。

通过将最小值指定为根，将剩余元素分成随机子集，并在每个子集上构建一个子树作为根的孩子，在随机元素集上构造一个随机二进制堆。 （由随机插入构造的堆的实际分布可能与此不同，但我猜测并不是这样的）。

在这个堆中插入一个随机元素x。扩展数组是O(1)分期付款，所以主要成本是堆积，这与流失元素的数量成正比。我们来计算一个期望值。

考虑到现有元素堆有n，新元素小于根的概率为1/(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为基数。）

Answer 2

您是否尝试过使用非随机输入（例如，在递增/递减数组）上运行add方法？它可以使其实际执行每个插入的动作~log n。随机输入可能不是这种情况，因为新添加的元素不可能是最大的元素，并且在添加随机元素时可能会一直到达根目录（可能会出现这种情况，即交换次数的预期值插入在这种情况下是一个常量，但我还没有尝试实际计算它）。