数据结构复习

//
// Advanced Algorithms and Data Structures
// TIEI - Fall 2024
//
package tiei.aads.bst;

import java.util.*;

/**
 * A class for binary search tree with rank
 */
public class RankedBST<AnyType extends Comparable<? super AnyType>> {

    // The tree root
	private BinaryNode root;

    /**
     * Construct the tree.
     */
    public RankedBST( ) {
        root = null;
    }

    /////////////// isEmpty

    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( ) {
        return root == null;
    }

    /////////////// makeEmpty

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty( ) {
        root = null;
    }

    /////////////// rank

    /**
     * Return the rank of x in the tree
     * @param x the element
     * @return the rank of x in the tree
     * if x is in the tree, 0 otherwise
     */
    public int rank(AnyType x) {
    	return rank(root,x);
    }

    /**
     * @brief 返回以t为根的树里x的排名
     * @note 复杂度：
     */
    private int rank(BinaryNode t, AnyType x) {
    	// --- 终止条件
        if ( t == null )
    		return 0;
    	if ( x.compareTo(t.element) == 0 )
    		return t.sizeOfLeft + 1;
        
        // --- 递归
    	if ( x.compareTo(t.element) < 0 )
    		return rank(t.left,x);     // x在t的左子树
    	int r = rank(t.right,x);       // x在t的右子树
    	if ( r == 0 )                  // 表示t.right是空树
    		return 0;                  // x不在t里，返回0？
    	return t.sizeOfLeft + 1 + r;
        //     ^^^ 比x小的   ^^ x  ^ 在右子树的排序
    }

    /////////////// element

    /**
     * Return the element of rank r in the tree
     * @param r the rank
     * @return the element of rank r in the tree
     * if such element exists, null otherwise
     */
    public AnyType element(int r) {
    	return element(root,r);
    }

    private AnyType element(BinaryNode t, int r) {
    	if ( t == null )
    		return null;
    	if ( t.sizeOfLeft + 1 == r )
    		return t.element;
    	if ( r <= t.sizeOfLeft )
    		return element(t.left,r);
    	return element(t.right,r - t.sizeOfLeft - 1);
    }

    /////////////// contains

    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return true if not found.
     */
    public boolean contains( AnyType x ) {
        return contains( x, root );
    }

    /**
     * Internal method to find an item in a subtree.
     * @param x is item to search for.
     * @param t the node that roots the subtree.
     * @return node containing the matched item.
     */
    private boolean contains( AnyType x, BinaryNode t ) {
        if( t == null )
            return false;

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 )
            return contains( x, t.left );
        else if( compareResult > 0 )
            return contains( x, t.right );
        else
            return true; // Match
    }

    /////////////// add

    /**
     * add into the tree; duplicates are ignored.
     * @param x the item to add.
     */
    public void add( AnyType x ) {
    	if ( ! contains(x) )
    		root = add( x, root );
    }

    /**
     * Internal method to add into a subtree.
     * @param x the item to add.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private BinaryNode add( AnyType x, BinaryNode t ) {
        if( t == null )
            return new BinaryNode( x );

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 ) {
            t.left = add( x, t.left );
            t.sizeOfLeft++;
        }
        else // WE KNOW THAT x IS NOT IN t
            t.right = add( x, t.right );
        return t;
    }

    /////////////// remove

    /**
     * Remove from the tree. Nothing is done if x is not found.
     * @param x the item to remove.
     */
    public void remove( AnyType x ) {
    	if ( contains(x) )
    		root = remove( x, root );
    }

    /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private BinaryNode remove( AnyType x, BinaryNode t ) {
    	// WE KNOW THAT x IS IN t
    	// if( t == null )
    	//   return t;   // Item not found; do nothing

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 ) {
            t.left = remove( x, t.left );
            t.sizeOfLeft--; // update the size of the left sub-tree
        }
        else if( compareResult > 0 )
            t.right = remove( x, t.right );
        else if( t.left != null && t.right != null ) // Two children
        {
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );
        }
        else
            t = ( t.left != null ) ? t.left : t.right;
        return t;
    }

    /**
     * Internal method to find the smallest item in a subtree.
     * @param t the node that roots the subtree.
     * @return node containing the smallest item.
     */
    private BinaryNode findMin( BinaryNode t ) {
        if( t == null )
            return null;
        else if( t.left == null )
            return t;
        return findMin( t.left );
    }

	////////////////////////////////////////////////////
	// Convenience method to print a tree
	////////////////////////////////////////////////////

    public void display() {
    	display(root,"","");
    }

    private void display(BinaryNode t, String r, String p) {
        if ( t == null ) {
            System.out.println(r);
        }
        else {
            String rs = t.element.toString();
            rs = "(" + t.sizeOfLeft + ")" + rs;
            System.out.println(r + rs);
            if ( t.left != null || t.right != null ) {
                String rr = p + '|' + makeString('_',rs.length()) + ' ';
                display(t.right,rr, p + '|' + makeString(' ',rs.length() + 1));
                System.out.println(p + '|');
                display(t.left,rr, p + makeString(' ',rs.length() + 2));
            }
        }
    }

    private String makeString(char c, int k) {
    	StringBuilder sb = new StringBuilder(k);
    	for ( int i = 0; i < k; i++ )
    		sb.append(c);
    	return sb.toString();
    }

	////////////////////////////////////////////////////
    // Inner class BinaryNode
	////////////////////////////////////////////////////

    // Basic node stored in unbalanced binary search trees
    private class BinaryNode {
            // Constructors
        BinaryNode( AnyType theElement ) {
            element  = theElement;
            left     = null;
            right    = null;
            sizeOfLeft = 0;
        }

        AnyType element;            // The data in the node
        BinaryNode left;   // Left child
        BinaryNode right;  // Right child

        int sizeOfLeft; // The size of the left subtree
    }

	////////////////////////////////////////////////////
	// Convenience methods to build a list of integer from a string
	////////////////////////////////////////////////////

    private static List<Integer> read(String inputString) {
    	List<Integer> list = new LinkedList<Integer>();
    	Scanner input = new Scanner(inputString);
    	while ( input.hasNextInt() )
    		list.add(input.nextInt());
    	input.close();
    	return list;
    }

    /**
     * A short main for quick testing
     */
    public static void main( String [ ] args ) throws EmptyTreeException {
    	List<Integer> list = read("50 30 70 20 40 80 60");
    	RankedBST<Integer> bst = new RankedBST<Integer>();
    	for ( Integer n : list )
    		bst.add(n);
    	bst.display();
    	System.out.println("Rank of 60: " + bst.rank(60));
    	System.out.println("Element of rank 6: " + bst.element(6));
    }
}

public class BinaryHeap<AnyType extends Comparable<? super AnyType>> {
	
	private AnyType[] A; // to store the heap
	private int size;    // the number of elements in the heap
	
	// comparator to choose
	private Comparator<AnyType> c = new Comparator<AnyType>() {
		public int compare(AnyType e1, AnyType e2) {
			return e1.compareTo(e2);
		}
	};
	
	///////////// Constructors
	
	/**
	 * Build a heap of capacity n.
	 * The elements are ordered according to the
	 * natural order on AnyType.
	 * The heap is empty.
	 * Complexity: THETA(1)
	 */
	public BinaryHeap(int n) {
		A = (AnyType[]) new Comparable[n];
		size = 0;
	}
	
	/**
	 * Build a heap of capacity n.
	 * The elements are ordered according to c.
	 * The heap is empty.
	 * Complexity: THETA(1)
	 */
	public BinaryHeap(int n, Comparator<AnyType> c) {
		this.A = (AnyType[]) new Comparable[n];
		this.size = 0;
		this.c = c;
	}
	
	/**
	 * Build a heap based on array A.
	 * The elements are ordered according to the
	 * natural order on AnyType.
	 * The heap is full
	 */
	public BinaryHeap(AnyType[] A) {
		this.A = A;
		this.size = A.length;
		buildHeap();
	}

	/**
	 * Build a heap based on array A.
	 * The elements are ordered according to c.
	 * The heap is full
	 */
	public BinaryHeap(AnyType[] A, Comparator<AnyType> c) {
		this.A = A;
		this.size = A.length;
		this.c = c;
		buildHeap();
	}
	
	///////////// Private methods
	
	/**
	 * Swap values in the array
	 * at indexes i and j.
	 * Complexity: THETA(1)
	 */
	private void swap(int i, int j) {
		AnyType tmp = A[i];
		A[i] = A[j];
		A[j] = tmp;
	}
	 
	/**
	 * Return the number of the left
	 * node of node number n.
	 * Complexity: THETA(1)
	 */
	private int left(int n) {
		return 2*n + 1;
	}
	
	/**
	 * Return the number of the right
	 * node of node number n.
	 * Complexity: THETA(1)
	 */
	private int right(int n) {
		return 2*(n + 1);
	}
	
	/**
	 * Return the number of the parent
	 * node of node number n.
	 * Complexity: THETA(1)
	 */
	private int parent(int n) {
		return (n - 1)/2;
	}
	
    private int getMaxChild(int n) {
		int lc = left(n);
		int rc = right(n);
		if(lc >= size && rc >= size) return -1; // 如果n是叶子节点，直接返回-1
		if(lc >= size) return rc;
		if(rc >= size) return lc;
		if(c.compare(A[lc], A[rc]) > 0) return lc;
		return rc;
	}
    
    /**
     * @brief 对下标为n的元素做“下沉”操作
     * @note Complexity: O(log(size))
     * @note 这是迭代/递归操作，执行完成后，原下标为n的元素应处在正确的位置上！
     * @param n 要进行下沉的元素下标
     */
	private void percolateDown(int n) {
		// int g = left(n);       // 左孩子的下标
        // int d = right(n);      // 右孩子的下标
        // int k = n;             // 迭代下标
		// if ( g < size && c.compare(A[g],A[n]) > 0 )
		//     k = g;
		// if ( d < size && c.compare(A[d],A[k]) > 0 )
		//     k = d;
		// if ( k != n ) {
		//     swap(k,n);
		//     percolateDown(k);  // 居然写成递归了，这样其实不太好
		// }
        // --- 改写为非递归形式
        int k = n;                // 迭代变量，迭代完成后会变成A[n]应处在的位置
		AnyType e = A[n];
		int maxChildIndex = getMaxChild(k);
		while((maxChildIndex != -1) && (k < size) && (c.compare(e, A[maxChildIndex]) < 0)) {
                                                     // ^^^ 注意，这里是按照最大堆写的，首元素是最大元素
			A[k] = A[maxChildIndex];
			k = maxChildIndex;
			maxChildIndex = getMaxChild(k);
		}
		A[k] = e;
	}
		
    /**
     * @brief 对下标为n的节点进行上浮操作
     * @note Complexity: O(log(size))
     * @note 这是迭代/递归操作，执行完成后，原下标为n的元素应处在正确的位置上！
     * @param n 下标
     */
	private void percolateUp(int n) {
		AnyType e = A[n];
		while ( n > 0 && c.compare(e,A[parent(n)]) > 0 ) {  // e大则上浮，相当于写成了最大堆
			A[n] = A[parent(n)];
			n = parent(n);
		}
		A[n] = e;
	}
	
	/**
	 * Arrange the elements in A such
	 * that it has the heap property.
	 * Complexity: O(size)
	 */
	private void buildHeap() {
		for ( int i = parent(size - 1); i >= 0; i-- )
			percolateDown(i);
	}
	
	///////////// Public methods
	
	/**
	 * Return the size of the heap
	 * (the number of elements in the heap).
	 * Complexity: THETA(1)
	 */
	public int size() {
		return size;
	}
	
	/**
	 * Check if the heap is empty.
	 * Complexity: THETA(1)
	 */
	public boolean isEmpty() {
		return size == 0;
	}
	
	/**
	 * Return the extreme element.
	 * Complexity: THETA(1)
	 */
	public AnyType extreme() throws EmptyHeapException {
		if ( size == 0 )
			throw new EmptyHeapException();
		return A[0];
	}
	
	/**
	 * Return and delete the extreme element.
	 * Complexity: O(log(size))
	 */
	public AnyType deleteExtreme() throws EmptyHeapException {
		if ( size == 0 )
			throw new EmptyHeapException();		
		AnyType extreme = A[0];
		A[0] = A[--size];           // 把尾元素放到（原）首元素处
		if ( size > 0 )
			percolateDown(0);       // 然后对首元素进行“下沉”操作
		return extreme;
	}
	
	/**
	 * Add a new element in the heap
	 * Complexity: O(log(size))
	 */
	public void add(AnyType e) throws FullHeapException {
		if ( size == A.length )
			throw new FullHeapException();		
		A[size++] = e;
		percolateUp(size-1);
	}
	
	///////////// Part 3: deleting in the heap
	
	/**
	 * Delete the element e from the heap.
	 * Complexity: O(size)
	 */
	public void delete(AnyType e) {
		for ( int i = 0; i < size; i++ )
			if ( A[i].compareTo(e) == 0 ) {
				A[i] = A[--size];
				percolateUp(i);
				percolateDown(i);
			} 
	}
	
	/**
	 * Delete all the elements e from the heap.
	 * Complexity: O(size)
	 */	
	public void deleteAll(AnyType e) {
		int i = 0;
		while ( i < size )
			if ( A[i].compareTo(e) == 0 )
				swap(i,--size);
		buildHeap();
	}
}

public class DynamicMedian<AnyType extends Comparable<? super AnyType>> {

	private BinaryHeap<AnyType> less;    // to store values less than or equal to the median
	private BinaryHeap<AnyType> greater; // to store values greater than or equal to the median

	/**
	 * Build a DynamicMedian object of maximum capacity n
	 */
	public DynamicMedian(int n) {
		Comparator<AnyType> c = new Comparator<AnyType>() {
			public int compare(AnyType e1, AnyType e2) {
				return e2.compareTo(e1);
			}
		};
		less = new BinaryHeap<AnyType>(n);         // 最大堆 用于存放比中值小的数
		greater = new BinaryHeap<AnyType>(n,c);    // 最小堆 用于存放比中值大的数
	}

	/**
	 * Return the size (the number of elements
	 * currently in the DynamicMedian object)
	 * Complexity: THETA(1)
	 */
	public int size() {
		return less.size() + greater.size();
	}

	/**
	 * Add a new element e.
	 * Complexity: O(log(size))
	 */
	public void add(AnyType e) throws EmptyHeapException, FullHeapException {
		if ( less.isEmpty() || e.compareTo(less.extreme()) <= 0 ) {
			less.add(e);                             // 如果这个新数比less里最大的小，那就把它放进less
			if ( less.size() > greater.size() + 1 )  // 如果less与greater个数相差大于1，
				greater.add(less.deleteExtreme());   // 就把less里最大的放进bigger
		}
		else {
			greater.add(e);                          // 否则 把它放进greater
			if ( less.size() < greater.size() )      // 从这里可以看出，less与greater要么数量相等，要么greater多一个
				less.add(greater.deleteExtreme());
		}
	}

	/**
	 * Return the current median.
	 * Complexity: THETA(1)
	 */
	public AnyType findMedian() throws EmptyHeapException {
		return less.extreme();                         // 存疑，如果greater比less多1，那么这样获得的就不是中间值
                                                       // 如果greater比less多1，应该返回greater的extreme
	}

	/**
	 * Return and delete the current median
	 * Complexity: O(log(size))
	 */
	public AnyType deleteMedian() throws EmptyHeapException, FullHeapException {
		AnyType median = less.deleteExtreme();
		if ( less.size() < greater.size() )
			less.add(greater.deleteExtreme());
		return median;
	}
}

public static <AnyType extends Comparable<AnyType>> void selection(AnyType[] array) {
	for ( int i = 0; i < array.length - 1; i++ ) { // i表示下一个最小值的存放位置
		int k = i; // k表示从i开始的最小值下标
		for ( int j = i + 1; j < array.length; j++ )
			if ( array[j].compareTo(array[k]) < 0 )
				k = j;
        // 现在k表示从i开始的最小值下标，把它放到i处
		swap(array, i, k);
	}
}

public static <AnyType extends Comparable<AnyType>> void insertion(AnyType[] array) {
	for ( int i = 1; i < array.length; i++ ) { // i表示第一个未排序元素的下标
		AnyType x = array[i];
		int j = i;                             // j表示array[i]的正确位置
		while ( j > 0 && array[j - 1].compareTo(x) > 0 ) {
			array[j] = array[j - 1];
			j = j - 1;
		}
        // 将array[i]放入正确位置
		array[j] = x;
	}
}

public class QuickSort {
	
	private static final int CUTOFF = 10;
	
	/**
	 * Sort the array in place using the quicksort algorithm
	 */
	public static <AnyType extends Comparable<AnyType>> void sort(AnyType[] array) {
		sort(array,0,array.length-1);
	}

	/**
	 * Sort the portion array[lo,hi] in place using the quicksort algorithm
	 */	
	private static <AnyType extends Comparable<AnyType>> void sort(AnyType[] array, int lo, int hi) {
		if ( hi - lo < CUTOFF )
			insertion(array,lo,hi);               // 切到小于CUTOFF时，就使用插入排序
		else {
			int pivot = partition(array,lo,hi);
			sort(array,lo,pivot - 1);
			sort(array,pivot + 1,hi);
		}
	}

	/**
	 * Partition the portion array[lo,hi] and return the index of the pivot
	 */
	private static <AnyType extends Comparable<AnyType>> int partition(AnyType[] array, int lo, int hi) {
		swap(array,lo,median(array,lo,(lo + hi)/2,hi));
                                                   // 对于这样的快速排序，其不稳定性可能是这一步造成的
                                                   // 只要能保证partition中相等元素的相对位置不变，那也可以是稳定的
		AnyType pivot = array[lo];
		int p = lo;                                // 下标p表示最后一个小于pivot的元素的下标，最终则刚好是pivot的下标
                                                   // 注意是++p，p先自增，自增后指向的元素就不一定是小于pivot的了
                                                   // 但是，交换完，p仍指向最后一个小于pivot的元素 
		for ( int i = lo + 1; i <= hi; i++ )       // 下标i从lo+1到hi循环
			if ( array[i].compareTo(pivot) < 0 )   // 如果下标i的元素小于pivot
				swap(array,i,++p);                 // 那么，先让p后移一个，然后让p、i处的元素交换
                                                   // Note: 之前提到k（即此处的i）表示第一个未处理的元素的下标
                                                   //       此for循环结束后，i的数值刚好为hi+1，并不矛盾
                                                   //       循环结束后，p指向的是最后一个严格小于pivot的元素
                                                   //       故交换并无不妥
		swap(array,lo,p);                          // 当然，最后要把pivot放到最终的p处，
                                                   // 进行完这一步后，下标p之前的元素都严格小于pivot
		return p;                                  // 最终返回
	}

	/**
	 * Return the index of the median of { array[lo], array[mid], array[hi] }
	 */
	private static <AnyType extends Comparable<AnyType>> int median(AnyType[] array, int lo, int mid, int hi) {
		if ( array[lo].compareTo(array[mid]) < 0 ) {
			if ( array[mid].compareTo(array[hi]) < 0 )
				return mid;
			if ( array[lo].compareTo(array[hi]) < 0 )
				return hi;
			return lo;
		}
		if ( array[lo].compareTo(array[hi]) < 0 )
			return lo;
		if ( array[mid].compareTo(array[hi]) < 0 )
			return hi;
		return mid;							
	}
	
	/**
	 * Sort array[lo, hi] in place using the insertion sort algorithm
	 */
	private static <AnyType extends Comparable<AnyType>> void insertion(AnyType[] array, int lo, int hi) {
		for ( int i = lo + 1; i <= hi; i++ ) {
			AnyType x = array[i];
			int j = i; 
			while ( j > lo && array[j - 1].compareTo(x) > 0 ) {
				array[j] = array[j - 1];
				j = j - 1;
			}
			array[j] = x;
		}
	}
	
	/**
	 * Swap array[i] and array[j]
	 */
	private static <AnyType> void swap(AnyType[] array, int i, int j) {
		AnyType tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}
}

public class MergeSort {

	/**
	 * Sort the array using the recursive merge sort algorithm.
	 * This algorithm is not in place and needs an auxiliary array of
	 * the same size than the array to sort
	 * Complexity: THETA( n.log(n) ) where n is the size of the array
	 */		
	public static <AnyType extends Comparable<AnyType>> void sort(AnyType[] array) {
		AnyType[] tmp = (AnyType[]) new Comparable[array.length];
		sort(array,tmp,0,array.length - 1);
	}
	
    /**
     * @brief 归并排序array[lo:hi]，使用tmp作为临时空间
     * @note 复杂度：THETA( n.log(n) ) where n = hi - lo + 1
     * @param tmp 临时空间，在merge时会用到
     * @param lo
     * @param hi
     */
	private static <AnyType extends Comparable<AnyType>> void sort(AnyType[] array, AnyType[] tmp, int lo, int hi) {
		if ( lo < hi ) {
			int mid = (lo + hi)/2;
			sort(array,tmp,lo,mid);     // 递归左半部分
			sort(array,tmp,mid + 1,hi); // 递归有半部分
			merge(array,tmp,lo,mid,hi); // 将排序好的左半部分和右半部分合并近tmp
			transfer(tmp,array,lo,hi);  // 从tmp拷贝回array
		}
	}
	
    /**
     * @brief 合并，其中array[lo:mid]是左半部分，array[mid+1:hi]是右半部分，使用tmp作为临时空间
     * @note 条件：array[lo, mid] and array[mid+1, hi] are sorted
     * @note 复杂度：THETA( n ) where n = hi - lo + 1
     * @note 注意：在merge时进行实际的排序
     * @param array 数组
     * @param tmp 临时空间，merge会merge到这里
     */
	private static <AnyType extends Comparable<AnyType>> void merge(AnyType[] array, AnyType[] tmp, int lo, int mid, int hi) {
		int l = lo;
		int r = mid + 1;
		int m = lo;
		while ( l <= mid && r <= hi )
			if ( array[l].compareTo(array[r]) < 0 )
				tmp[m++] = array[l++];   // 如果array[l]更小，就写入array[l]
                                         // Note: 这里没有等于，是不是导致这种写法不是稳定的归并排序？这里应该有等于，才是稳定的归并排序
			else
				tmp[m++] = array[r++];   // 否则写入array[r]
		while ( l <= mid )
			tmp[m++] = array[l++];
		while ( r <= hi )
			tmp[m++] = array[r++];
	}

	/**
	 * Copy the elements from tmp[lo, hi] into array[lo, hi]
	 * Complexity: THETA( n ) where n = hi - lo + 1
	 */
	private static <AnyType> void transfer(AnyType[] tmp, AnyType[] array, int lo, int hi) {
		for ( int i = lo; i <= hi; i++ )
			array[i] = tmp[i];
	}
}

public class MergeSort2 {
	/**
	 * Sort the array using the recursive merge sort algorithm.
	 * This algorithm is not in place and needs an auxiliary array of
	 * the same size than the array to sort
	 * Complexity: THETA( n.log(n) ) where n is the size of the array
	 */		
	public static <AnyType extends Comparable<AnyType>> void sort(AnyType[] array) {
		AnyType[] tmp = (AnyType[]) new Comparable[array.length];
		sortInplace(array,tmp,0,array.length - 1);
	}
	
    /**
     * @brief 对array[lo:hi]原地排序
     * @note 先把左右两部分排序到tmp里，然后再merge到array里
     */
	private static <AnyType extends Comparable<AnyType>> void sortInplace(AnyType[] array, AnyType[] tmp, int lo, int hi) {
		if ( lo < hi ) {
			int mid = (lo + hi)/2;
			sortTo(array,tmp,lo,mid);           // 不再是直接递归自己，而是调用sortTo，然后让sortTo再调用sortInplace
			sortTo(array,tmp,mid + 1,hi);
			mergeTo(tmp,array,lo,mid,hi);       // 相较于MergeSort1省去了transfer
		}
	}
	
    /**
     * @brief 把array[lo:hi]排序到tmp里面
     * @note 先把左右两部分都“原地”排序，再合并到tmp里
     * @note Complexity: THETA( n.log(n) ) where n = hi - lo + 1
     */
	private static <AnyType extends Comparable<AnyType>> void sortTo(AnyType[] array, AnyType[] tmp, int lo, int hi) {
		if ( lo < hi ) {
			int mid = (lo + hi)/2;
			sortInplace(array,tmp,lo,mid);
			sortInplace(array,tmp,mid + 1,hi);
			mergeTo(array,tmp,lo,mid,hi);
		}
		else if ( lo == hi )
			tmp[lo] = array[lo];
	}
	
    /**
     * @brief 将from[]数组合并进to[]数组
     * @note Complexity: THETA( n ) where n = hi - lo + 1
     * @note Precondition: array[lo, mid] and array[mid+1, hi] are sorted
     * @param from
     * @param to
     * @param lo
     * @param mid
     * @param hi
     */
	private static <AnyType extends Comparable<AnyType>> void mergeTo(AnyType[] from, AnyType[] to, int lo, int mid, int hi) {
		int l = lo;
		int r = mid + 1;
		int m = lo;
		while ( l <= mid && r <= hi )
			if ( from[l].compareTo(from[r]) < 0 )
				to[m++] = from[l++];
			else
				to[m++] = from[r++];
		while ( l <= mid )
			to[m++] = from[l++];
		while ( r <= hi )
			to[m++] = from[r++];
	}

}

public class RootFinder {
	
	private static DiGraph G;
	private static Set<Vertex> visited;
	
	/**
	 * Returns a root of the graph 'G' if
	 * such root exists, null otherwise
	 */
	public static Vertex findRoot(DiGraph G) {
		RootFinder.G = G;
		RootFinder.visited = new HashSet<Vertex>();
		
		Vertex candidate = candidate();            // 找出有可能成为根节点的节点
		
		visited.clear();
		if ( visit(candidate) == G.nbVertices() )
			return candidate;
		return null;
	}
	
	/**
	 * @brief 获得一个潜在的根节点
	 * @note 思路：从每个未访问过的节点开始进行DFS访问，返回最后一次visit的节点
	 * @return Returns a root candidate
	 */
	private static Vertex candidate() {
		Vertex last = null;
		for ( Vertex u : G.vertices() )
			if ( ! visited.contains(u) ) {         // 对于每个没访问过的节点u
				last = u;                          // 记录这个节点
				visit(u);                          // 访问它
			}
		return last;                               // 经过遍历后，last是唯一可能作为root的节点
                                                   // Note: 容易看出，在循环中，如果根节点存在，last就一定曾是根节点
                                                   //       而假设某次迭代中last = u是根节点，那么visit(u)后所有节点
                                                   //       都被访问过了，不可能再有没被访问过的节点u覆盖last，因此
                                                   //       最终的跟节点只可能出现在最终的last上
	}
	
    /**
     * @brief DFS递归函数，返回以u为起点可以经过的不同节点数量
     * @param u 起始节点
     * @return integer, 以u为起点可以经过的不同节点数量
     */
	private static int visit(Vertex u) {
		visited.add(u);
		int n = 1;
		for ( Vertex a : G.adjacents(u) )
			if ( ! visited.contains(a) )
				n += visit(a);
		return n;
	}
	
	public static void main(String[] s) {
		DiGraph G = GraphReader.D2;
		System.out.println(findRoot(G));
	}	
}

public class PathFinder {
	
	private static Graph G;
	
	private static Set<Vertex> visited;
	
	/**
	 * Returns a path as from vertex 'u' to vertex 'v' in the graph 'G'
	 * as a list of vertices if such a path exists, the empty list otherwise
	 */
	public static List<Vertex> findPath(Graph G, Vertex u, Vertex v) {
		PathFinder.G = G;
		PathFinder.visited = new HashSet<Vertex>();
		
		List<Vertex> path = new LinkedList<Vertex>();
		
		findPath(u,v,path);
		return path;
	}
	
	/**
	 * If there is a path from vertex 'u' to vertex 'v' in the graph, the
	 * vertices of this path are stored in the list 'path' and the method
	 * returns true. Else the list 'path' remains unchanged and the method
	 * returns false
	 */
	private static boolean findPath(Vertex u, Vertex v, List<Vertex> path) {
		visited.add(u);
		if ( u == v ) {
			path.add(u);
			return true;
		}
		for ( Vertex a : G.adjacents(u) ) {
			if ( ! visited.contains(a) ) {
				if ( findPath(a,v,path) ) {
					path.add(0,u);
					return true;
				}
			}
		}
		return false;
	}
	
	public static void main(String[] s) {
		DiGraph G = GraphReader.D3;
		System.out.println(G);
		
		System.out.println(findPath(G,G.getVertex("F"),G.getVertex("E")));
	}
}

/**
 * A class to find cycles in undirected and directed graphs
 */
public class Cycles {
	
	private static Graph G;
	
	/////////////// Cycle detection for undirected graphs
	
	private static Set<Vertex> visited;
	
	/**
	 * Returns true if the graph 'G' is cyclic
	 * false otherwise
	 */
	public static boolean hasCycle(UnDiGraph G) {
		visited = new HashSet<Vertex>();
		Cycles.G = G;
		
		for ( Vertex u : G.vertices() )
			if ( ! visited.contains(u) )
				if ( hasCycle(u,null) )
					return true;
		return false;
	}
	
    /**
     * @brief 判断以from节点为起点是否存在环路
     * @note 假定节点from已经被访问过，节点u未被访问过
     * @note 另有隐含条件：from与u一定是相邻的，或者from为null
     * @param u 
     * @param from
     * @return true: 从from到u有环 false: 无
     */
	private static boolean hasCycle(Vertex u, Vertex from) {
		visited.add(u);                    // 将u加入已访问集合
		for ( Vertex a : G.adjacents(u) )  // 遍历与u相邻的节点a
			if ( ! visited.contains(a) ) {
				if ( hasCycle(a,u) )       // 对于每一个与u相邻且未访问过的节点，判断从u到该节点是否有环
					return true;           // 如果有环，立即返回true
			} else                         // Note: 此分支中，隐含a处在visited集合中这一条件
                if ( a != from )           //       如果a != from则意味着u的邻居a是一个已访问过的节点
                                           //       如果a刚好为from，无法说明有环路，因为存在隐含条件即from与u相邻
					return true;
		return false;                      // 否则返回false
	}
	
	/////////////// Cycle detection for directed graphs
	
	private enum Status { UnDiscovered, InProgress, Completed } // status of vertex
	
	private static Map<Vertex,Status> vertexStatus; // to set the status of each vertex

	/**
	 * Returns true if the graph 'G' is cyclic
	 * false otherwise
	 */
	public static boolean hasCycle(DiGraph G) {
		vertexStatus = new HashMap<Vertex,Status>();
		Cycles.G = G;
		
		for ( Vertex u : G.vertices() )      // 对于图中的每个节点u
			if ( status(u) == Status.UnDiscovered )
				if ( hasCycle(u) )           // 如果它的状态是UnDiscovered那么就对该节点进行判定
					return true;
		return false;
	}
	
	/**
	 * Returns true if a cycle was found by traversing
	 * the graph from vertex u
	 * Precondition: vertex 'u' is 'UnDiscovered'
	 */
    /**
     * @brief 以u为起点判定有向图是否有环
     */
	private static boolean hasCycle(Vertex u) {
		setStatus(u,Status.InProgress);       // 更新节点u的状态为InProgress
		for ( Vertex a : G.adjacents(u) )     // 对于节点u的每个邻接节点a
			if ( status(a) == Status.UnDiscovered ) {
                                              // 如果节点a的状态为UnDiscovered，那么对a进行判定
				if ( hasCycle(a) )
					return true;
			}
			else if ( status(a) == Status.InProgress )
                                              // Note: 如果a的状态为InProgress则表示“u是从a到达的”
                                              //       也可理解为hasCycle(a)尚未返回，仍处在调用栈中
                                              //       然而我们从u又可达a，从而说明有环路
				return true;
		setStatus(u,Status.Completed);        // 如果到这儿了，表示以u为起点，找不到环路，我们将u的状态标记为Completed
		return false;
	}
	
	
	/**
	 * Returns the status of vertex 'u'
	 */
	private static Status status(Vertex u) {
		Status s = vertexStatus.get(u);
		if ( s == null )
			return Status.UnDiscovered;
		return s;
	}
	
	/**
	 * Sets the status of vertex 'u' to 's'
	 */	
	private static void setStatus(Vertex u, Status s) {
		vertexStatus.put(u,s);
	}
	
}

public class BFS {
	
	private DiGraph G;
	
	public BFS(DiGraph G) {
		this.G = G;
	}
	
	public List<Vertex> bfs(Vertex start) {
		Queue<Vertex> queue = new LinkedList<>();        // BFS队列
		List<Vertex> result = new LinkedList<>();        // 用于存储遍历顺序的列表
		Set<Vertex> marked = new HashSet<>();            // 用于记录已经访问过的节点
		// 1 --- 初始化
        marked.add(start);
		queue.offer(start);
        // 2 --- 执行算法
		while ( ! queue.isEmpty() ) {
			Vertex v = queue.poll();
			result.add(v);
			for ( Vertex a : G.adjacents(v) ) {
				if ( ! marked.contains(a) ) {
					marked.add(a);
					queue.offer(a);
				}
			}
		}
		return result;
	}
	
	public Map<Vertex,Integer> distance(Vertex start) {
		Queue<Vertex> queue = new LinkedList<>();
		Map<Vertex,Integer> distance = new HashMap<>();  // 用于存储节点到距离的映射
		// 1 --- 初始化
        distance.put(start, 0);                          
		queue.offer(start);                              // 初始化BFS队列，首先放入起始节点
		// 2 --- 执行算法
        while ( ! queue.isEmpty() ) {
			Vertex v = queue.poll();
			for ( Vertex a : G.adjacents(v) ) {
				if ( ! distance.containsKey(a) ) {
					distance.put(a, distance.get(v) + 1);// 与单源最短路区分，这里的边没有权重
					queue.offer(a);
				}
			}
		}
		return distance;
	}

}

public class TopSort {
	
	/**
	 * Returns the list of vertices of 'G' in
	 * (one) topological order
	 */
	public static List<Vertex> sort1(DiGraph G) {
        // --- 寻找入度为0的节点作为起始节点
		Map<Vertex,Integer> inDegree = new HashMap<Vertex,Integer>();
		Queue<Vertex> queue = new LinkedList<Vertex>();
                                                    // 存储可以用作下一次算法的起始节点的集合
		List<Vertex> sorted = new LinkedList<Vertex>();
                                                    // 存储拓扑排序
		for ( Vertex vertex : G.vertices() ) {
			inDegree.put(vertex,G.inDegree(vertex));
			if ( G.inDegree(vertex) == 0 )
				queue.offer(vertex);
		}
		while ( ! queue.isEmpty() ) {
			Vertex v = queue.poll();
			sorted.add(v);
			for ( Vertex a : G.adjacents(v) ) {
				inDegree.put(a,inDegree.get(a)-1);  // 伪“删边”
				if ( inDegree.get(a) == 0 )         // 一个入度为0的节点可以作为起始节点
					queue.offer(a);
			}
		}
		return sorted;
	}
	
	/**
	 * Returns the list of vertices of 'G' in
	 * (one) topological order
	 */
	public static List<Vertex> sort2(DiGraph G) {
		Set<Vertex> visited = new HashSet<Vertex>();
		List<Vertex> sorted = new LinkedList<Vertex>();
		for ( Vertex v : G.vertices() )
			if ( ! visited.contains(v) )
				visit(G,v,visited,sorted);
		return sorted;
	}
	
	/**
	 * Visit the digraph 'G' using DFS from vertex 'u' and add all the visited
	 * vertices in 'sorted' such that they appear in topological order
	 */
	private static void visit(DiGraph G, Vertex u, Set<Vertex> visited, List<Vertex> sorted) {
		visited.add(u);
		for ( Vertex a : G.adjacents(u) )
			if ( ! visited.contains(a) )
				visit(G,a,visited,sorted);
		sorted.add(0,u);
	}
	
	/**
	 * Test if the digraph G has an Hamiltonian path
	 */
	public static boolean hasHamiltonianPath(DiGraph G) {
		List<Vertex> topo = sort1(G);
		Vertex previous = topo.removeFirst();
		for ( Vertex v : topo ) {                   // 拓扑排序相邻相连 <=> 具有哈密顿路径
			if ( ! G.adjacents(previous, v) )
				return false;
			previous = v;
		}
		return true;
	}
}

public class MST {
	
	/**
	 * Returns the list of edges of an MST of weighted undirected graph G
	 * * using the Prim algorithm
	 * Precondition: G is connected
	 */
	public static List<Edge> prim(UnDiGraph G) throws FullHeapException, EmptyHeapException {
		List<Edge> mst = new LinkedList<Edge>();   // MST的边集合
		Comparator<Edge> c = new Comparator<Edge>() {
                                                   // 建立最小堆
                                                   // 堆中存储与known集合相邻的边
			public int compare(Edge e1, Edge e2) {
				return e2.compareTo(e1);
			}
		};
		BinaryHeap<Edge> minHeap = new BinaryHeap<Edge>(G.nbEdges(),c);
		Set<Vertex> known = new HashSet<Vertex>(); // 存储已知节点的集合
        // --- 从任意节点开始算法
		Vertex u = G.getRandomVertex();
		known.add(u);
		// 将与u相连的边加入最小堆
		for ( Edge e : G.incidents(u) )
			minHeap.add(e);
		// while not all vertices are known (i.e. connected)
		while ( known.size() < G.nbVertices() ) {
			Edge min = minHeap.deleteExtreme();
			Vertex x = notKnown(min,known);
			if ( x != null ) {
                                                   // min是know集合与其他节点相连的边
				mst.add(min);                      // 那么将它加入最小生成树
				known.add(x);                      // 并将新节点加入know集合
				for ( Edge e : G.incidents(x) ) {
					Vertex y = notKnown(e,known);
					if ( y != null )
						minHeap.add(e);            // 并将与新节点相连的、连接到其他节点的边加入堆
				}
			}
		}
		return mst;
	}
	
	/**
	 * Given the edge 'e' = (u,v) and the current set of known vertices
	 * returns the vertex (u or v) which is not in 'know', or null if they
	 * are both in 'known'
	 * Precondition: if 'e' = (u,v), at least one of u and v is in 'known'
	 */
	private static Vertex notKnown(Edge e, Set<Vertex> known) {
		Vertex v = null;
		if ( ! known.contains(e.origin()) )
			v = e.origin();
		else if ( ! known.contains(e.destination()))
			v = e.destination();
		return v;
	}

}

public class MST {
	
	/**
	 * Returns the list of edges of an MST of weighted undirected graph G
	 * using the Kruskal algorithm
	 * Precondition: G is connected
	 */
	public static List<Edge> kruskal(UnDiGraph G) throws FullHeapException, EmptyHeapException {
		List<Edge> mst = new LinkedList<Edge>(); 
		Comparator<Edge> c = new Comparator<Edge>() {
			public int compare(Edge e1, Edge e2) {
				return e2.compareTo(e1);
			}
		};
		BinaryHeap<Edge> minHeap = new BinaryHeap<Edge>(G.nbEdges(),c);
		for ( Edge e : G.edges() )                     // 将所有边加入堆
			minHeap.add(e);
		// disjoint sets of all the vertices of the graph G
		Partition<Vertex> P = new Partition<Vertex>();
		// add each vertex as a new tree in the partition
		for ( Vertex v : G.vertices() )
			P.newTree(v);                              // 将每个节点初始化作为一个“孤岛”
		// while not all the vertices are connected
		while ( P.nbTrees() > 1 ) {                    // 只要“孤岛”的数量大于1,就表示生成树没有找完
			Edge min = minHeap.deleteExtreme();        // 1 - 寻找权重最小的边
			Vertex u = min.origin();
			Vertex v = min.destination();
			Partition.Tree ru = P.find(u);
			Partition.Tree rv = P.find(v);
			if ( ru != rv ) {                           // 2 - 检查它是否连接两个孤岛
				mst.add(min);                           //     如果是，就将它放入最小生成树，
				P.union(ru, rv);                        //     并将它连接的两个“孤岛”进行union操作
			}
		}
		return mst;
	}

}

public class Partition<AnyType> {

	private int nbTrees;                    // 当前并查集的分区数
	private Map<AnyType,InnerTree> map;     // 将每个对象映射到它所属的树
	
	/**
	 * Return an empty partition with no tree
	 */
	public Partition() {
		nbTrees = 0;
		map = new HashMap<AnyType,InnerTree>();
	}
	
	public int nbTrees() {
		return nbTrees;
	}
	
	/**
	 * Add a new one-element tree with
	 * element 'e' in the partition
	 */
	public void newTree(AnyType e) {
		map.put(e,new InnerTree());
		nbTrees++;
	}
	
	/**
	 * Returns the tree the
	 * element 'e' belongs to
	 */
	public Tree find(AnyType e) {
		return find(map.get(e));
	}
	
	/**
	 * Merge the two trees 'x' and 'y'
	 * Precondition: 'x' != 'y'
	 */
	@SuppressWarnings("unchecked")
	public void union(Tree x, Tree y) {
		union((InnerTree) x, (InnerTree) y);
	}
	
	/**
	 * Merge the two InnerTree 'x' and 'y'
	 * Precondition: 'x' != 'y'
	 */	
	private void union(InnerTree x, InnerTree y) {
		if ( x.size <= y.size ) {
			x.parent = y;
			y.size += x.size;
		}
		else {
			y.parent = x;
			x.size += y.size;
		}
		nbTrees--;
	}
	
	/**
	 * Returns the root InnerTree the
	 * (sub-tree) InnerTRee 'n' belongs to
	 */
	private InnerTree find(InnerTree n) {
		if ( n == n.parent )
			return n;
		InnerTree root = find(n.parent);
		n.parent = root;
		return root;
	}
	
	/**
	 * A public interface to provide the Partition.Tree type
	 * to the client code. There is NO operation available
	 * on Partition.Tree, except reference comparison == and !=
	 */
	public interface Tree {}
	
	/**
	 * A (private) class for InnerTree
	 */
	private class InnerTree implements Tree {
		
		// the InnerTree parent
		InnerTree parent;
		// the number of elements inside this InnerTree
		int size;
		
		/**
		 * Returns a single-element InnerTree
		 */
		InnerTree() {
			this.parent = this;
			this.size = 1;
		}
	}
}

public class Dijkstra extends ShortestPath{
		
	public Dijkstra(Graph G, Vertex start) {
		super(G,start);
	}
	
    /**
     * @brief 使用Dijkstra算法寻找最短路径
     */
	public void computeShortestPaths() {
        // Note:
        //       复杂度O((|V|+|E|)log|V|)，因为每个节点与每条边都被访问一遍，percolateUp是logV
        //       O(|V|log|V| + |E|log|V|)
        
		// Note: 图中的每个节点都对应一个权重，这个权重的含义是**目前已探明**的该节点距离起始节点的最短距离
        //       因此，初始化所有节点的权重为无穷大，表示在初始情况下，我们认为所有节点都不可达
        // 1 --- 初始化权重
		Set<Vertex> known = new HashSet<>();  // 建立一个保存“已知”节点的集合
		for ( Vertex v : G.vertices() )       // 首先，将每个节点的“权重”都设置为无穷大
			v.setWeight(Double.POSITIVE_INFINITY);
		start.setWeight(0.0);                 // 然后，将起始节点的权重设置为0，显然起始节点到它自己的最短权重为0
		
        
        // Note: 由于算法的流程，我们经常要从未知集合里取出一个权重最小的节点，因此我们使用一个修改过的堆来管理所有节点
        // 2 -- 初始化堆
                                              // 初始化一个堆
		DijkstraHeap heap = new DijkstraHeap(G.nbVertices());
		for ( Vertex v : G.vertices() )       // 然后将所有节点放入堆
			heap.add(v);
        
        // 3 -- 执行算法
		while ( known.size() != G.nbVertices() ) {
                                              // 已知节点数不等于全部节点数，表示还有未探明的节点
			Vertex min = heap.deleteMin();    // 从堆中取出并删除一个权重最小的节点
			known.add(min);                   // 然后把这个节点加入“已知节点集合”
                                              // Note: 可以证明，该节点的权重已经为最小，因此它可以被加入“已探明节点”集合
                                              //       由于我们探明了新的节点，因此与新探明节点相邻的未知节点权重可能需要更新
			for ( Edge e : G.incidents(min) ) {
				Vertex v = e.otherEnd(min);
				if ( ! known.contains(v) ) {
                                              // 遍历与“新探明节点”相邻的未知节点
					double newDist = min.getWeight() + e.weight();
                                              // 计算由于新探明节点而产生的新路径上的权重
					if ( newDist < v.getWeight() ) {
						v.setWeight(newDist); // 如果新路径上的权重更小，那就更新这个节点的权重为新路径的权重
						edgeTo.put(v, min);   // 以及更新路径
                                              // Note: edgeTo哈希表记录了从起始节点到每个节点最短路径的“上一跳”
                                              //       其key是起始节点以外的任意节点，其value是到达该节点最短路径的上一步
                                              //       有了这个哈希表，在算法执行完成后，我们可以得出从起始节点到任意节点的最短路径
						heap.percolateUp(v);  // 当然，由于权重更新了，还要将这个节点在堆中进行“上浮”操作 log(V)
					}
				}
			}
		}
	}
	
	/**
	 * A main for quick testing
	 */
	public static void main(String[] args) {
		Graph G = GraphReader.WD4;
		Vertex start = G.getVertex("S");
		Dijkstra d = new Dijkstra(G,start);
		d.computeShortestPaths();
		
		for ( Vertex v : G.vertices() )
			System.out.print(v + ": " + v.getWeight() + "  ");
		System.out.println("\n");
		for ( Vertex v : G.vertices() )
			System.out.println(start + " to " + v + ": " + d.shortestPath(v));
		
	}
}