技术

算法4 Java解答 5.1.2

HuGuoDong
技术, 归档
5.1.2 问题： 给出使用地位优先的字符串排序算法处理下面这些键的轨迹 no is th ti fo al go pe to co to th ai of th pa Give a trace for LSD string sort for the keys: no is th ti fo al go pe to co to th ai of th pa 分析： LSD 适用于字符等长的数组排序。 从右往左，依次数组中每个元素对位置d的字符使用key-indexed counting排序。 平均数组访问次数7WN+3WR。额外空间N+R。 N 对应aux数组，R对应count数组。 对于一般的应用LSD线性时间复杂度。 public static void sort(String[] a, int w) { int N = a.length; int R = 256; String[] aux = new String[N]; for (int d = w - 1; d >= 0; d--) { // sort by key-indexed counting on dth char show(a); int[] count = new int[R + 1]; for (int i = 0; i < N; i++) { count[a[i].

算法4 Java解答 2.4.24

HuGuoDong
技术, 归档
2.4.24 问题： Priority queue with explicit links. Implement a priority queue using a heap- ordered binary tree, but use a triply linked structure instead of an array. You will need three links per node: two to traverse down the tree and one to traverse up the tree. Your implementation should guarantee logarithmic running time per operation, even if no maximum priority-queue size is known ahead of time. 使用链表的优先队列。使用二叉树实现一个优先队列。每个结点都需要三个链接：两个向下，一个向上。你的实现需要保证在无法预知队列大小的情况下也能保证优先队列的基本操作所需要的时间为对数级别。 分析： 插入\删除 ：

算法4 Java解答 2.4.22

HuGuoDong
技术, 归档
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.

算法4 Java解答 2.4.21

HuGuoDong
技术, 归档
2.4.21 问题： 2.4.21 Elementary data structures. Explain how to use a priority queue to implement the stack, queue, and randomized queue data types from Chapter 1 分析： 题目要求使一个优先队列。 假设使用MaxPQ优先队列的操作有 insert delMax isEmpty size Stack： 那么对于Stack LIFO 的实现我们需要指定被后插入的元素的priority比之前插入的元素priority大。 Queue: 对于Queue FIFO 的实现，需要后插入元素的priority小于之前插入元素的priority。 randomized queue： 随机队列需要指定一个随机的priority，其余实现和处理Queue的方法一样。 问题是怎么样生成一个不重复的随机数呢？我的思路是使用一个Set保存随机数。 public int random() { int num = 0; while (!numSet.contains(num)) { num = StdRandom.uniform(1, Integer.MAX_VALUE); numSet.add(num); break; } return num; } 另外要提到的是对于使用MaxPQ实现的Stack和Queue，插入删除元素的时间复杂度都是lgN。 class IKey implements Comparable<IKey>{ Key value; int priority; @Override public int compareTo(IKey another) { return compare(this.