算法4 Java解答 2.4.22

HuGuoDong

October 31, 2018

Page content

2.4.2

问题：

2.4.22 Array resizing. Add array resizing to MaxPQ, and prove bounds like those of Proposition Q for array accesses, in an amortized sense.

调整数组的大小。在MaxPQ中加入调整数组大小的代码，并和命题Q一样证明对于一般性长度为N的队列数组访问的上限。

分析：

在MaxHeap类中新增方法 resize(int max)，当堆的中元素个数等于key数组容量满的时候，key数组增大两倍，当堆的元素个数等于key数组长度的1/4时，key数组长度变为原来的1/2.


  public _MaxMQ(){
    this(1);
  }

  private void resize(int max){
    assert max > N;
    Comparable[] temp = new Comparable[max];
    for(int i=1; i<=N; i++){
      temp[i] = pq[i];
    }
    pq = (Key[]) temp;
  }

    public Key delMax(){
      Key max = pq[1];
      pq[1] = pq[N--];  // 使用 pq[N] 作为哨兵
      sink(1);
      pq[N + 1] = null;

      if(N==(pq.length-1)/4) resize(pq.length/2);

      assert isMaxHeap();
      return max;
    }

    public void insert(Key v){
      // double size of array is necessary
      if(N==(pq.length-1)) resize(pq.length*2);

      pq[++N] = v;
      swim(N);
    }

  public static void main(String[] args) {
    for(int i=0; i<3; i++){
      _MaxMQ<Integer> pq = new _MaxMQ<>();
      Integer[] a = ascIntArray(10*i);
      for(int j=0; j<a.length; j++){
        pq.insert(j);
      }

      while (!pq.isEmpty()){
        StdOut.printf("%5d\t", pq.delMax());
      }

      StdOut.println();
    }
  }
//    9	    8	    7	    6	    5	    4	    3	    2	    1	    0
//        19	   18	   17	   16	   15	   14	   13	   12	   11	   10	    9	    8	    7	    6	    5	    4	    3	    2	    1	    0