/**
 * Company
 * Copyright (C) 2014-2017 All Rights Reserved.
 */
package com.cwenao.datastructure.queue;

import java.util.Iterator;

/** 索引优先队列：在优先队列的基础上加上优先队列中值在qp中对应的索引
 *
 * @author cwenao
 * @version $Id IndexMinPQ.java, v 0.1 2017-09-02 23:33 cwenao Exp $$
 */
public class IndexMinPQ<T extends Comparable> implements Iterable{

    private int maxLen; //PQ的最大长度
    private static final int DEFAULT_MAX_LEN = 20;
    private int len; //PQ长度
    private int pq[]; // 优先队列
    private int qp[]; // 优先队列值映射列表
    private T[] keys; // 真实元素队列

    public IndexMinPQ() {
        this(DEFAULT_MAX_LEN);
    }

    public IndexMinPQ(int maxLen) {
        this.maxLen = maxLen;
        pq = new int[maxLen + 1];
        qp = new int[maxLen + 1];
        keys = (T[]) new Comparable[maxLen + 1];
        len = 0;

        for (int i=0;i<=maxLen;i++) {
            qp[i] = -1;
        }
    }

    private void swim(int k) {
        while (k > 1 && greater(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while (2 * k <= len) {
            int j = 2 * k;
            if (j < len && greater(j, j + 1)) {
                j++;
            }
            if (!greater(k, j)) {
                break;
            }
            exch(k, j);
            k = j;
        }
    }

    private boolean greater(int source, int target) {
        return keys[pq[source]].compareTo(keys[pq[target]]) > 0;
    }

    private void exch(int source, int target) {
        int tmp = pq[source];
        pq[source] = pq[target];
        pq[target] = tmp;
        qp[pq[source]] = source;
        qp[pq[target]] = target;
    }

    @Override
    public Iterator iterator() {
        return null;
    }

}

@@ -877,32 +877,552 @@
        %7D%0A    %7D%0A%0A
+    public void insert(int i, T key) %7B%0A%0A        len++;%0A        qp%5Bi%5D = len;%0A        pq%5Blen%5D = i;%0A        keys%5Bi%5D = key;%0A        swim(len);%0A%0A    %7D%0A%0A    public int delMin() %7B%0A        int min = pq%5B1%5D;%0A        exch(1, len--);%0A        sink(1);%0A        qp%5Bmin%5D = -1;%0A        keys%5Bpq%5Bmin%5D%5D = null;%0A        pq%5Blen + 1%5D = -1;%0A%0A        return min;%0A    %7D%0A%0A    public T keysOf(int i) %7B%0A        return keys%5Bi%5D;%0A    %7D%0A%0A    public void changeKey(int i, T key) %7B%0A        keys%5Bi%5D = key;%0A        swim(qp%5Bi%5D);%0A        sink(qp%5Bi%5D);%0A%0A    %7D%0A%0A
     private void
@@ -1428,32 +1428,32 @@
 d swim(int k) %7B%0A
-
         while (k
@@ -1572,32 +1572,33 @@
 d sink(int k) %7B%0A
+%0A
         while (2
@@ -1836,16 +1836,16 @@
  k = j;%0A
-
         
@@ -1845,32 +1845,83 @@
        %7D%0A    %7D%0A%0A
+    public int size() %7B%0A        return len;%0A    %7D%0A%0A
     private bool

update the IndexMinPQ