使用最小優先級隊列的複雜性問題

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。隨機輸入可能不是這種情況，因爲新添加的元素不可能是最大的元素，並且在添加隨機元素時可能會一直到達根目錄（可能會出現這種情況，即交換次數的預期值插入在這種情況下是一個常量，但我還沒有嘗試實際計算它）。