优先队列
public class Priority_queue { private int[] a; private int count; Priority_queue(int[] b) { a = new int[b.length + 1]; for (int i = 1; i < a.length; ++i) a[i] = b[i - 1]; count = b.length; //形成堆 for (int k = count / 2; k >= 1; --k) sink(k,count); //a[0] for 哨兵 sentry } private void sink(int k,int N) { while (2 * k <= N) { int j = 2 * k; while (j < N && a[j] < a[j + 1]) ++j; if (a[k] > a[j]) break; int temp = a[j]; a[j] = a[k]; a[k] = temp; k = j; } } private void swim(int k) { while (k > 1 && a[k] > a[k / 2]) { int temp = a[k]; a[k] = a[k / 2]; a[k / 2] = temp; k = k / 2; } } public boolean isEmpty() { return count == 0; } private void resize(int n) { int[] temp = new int[n]; for (int i = 1; i <= count; ++i) temp[i] = a[i]; a = temp; } public Object deleteMax() { if (isEmpty()) return null; int ret = a[1]; a[1] = a[count]; a[count--] = 0; sink(1,count); if (count == a.length / 4) resize(a.length / 2); return ret; } public boolean isFull() { return count == a.length - 1; } public void insert(int i) { if (isFull()) resize(2 * count); a[++count] = i; swim(count); } }堆排序
import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; public class HeapSort { private int[] a; public HeapSort(int N) { a = new int[N]; for (int i = 0; i < N; ++i) a[i] = StdRandom.uniform(-15*N,15*N); } public HeapSort(int[] b) { a = new int[b.length]; for (int i = 0; i < a.length; ++i) a[i] = b[i]; } public void sink(int k,int N) { while (2*k + 1 <= N) { int j = 2 * k + 1; while (j < N && a[j] < a[j + 1]) ++j; if (a[k] > a[j]) break; int temp = a[j]; a[j] = a[k]; a[k] = temp; k = j; } } public void sort() { int N = a.length - 1; for (int k = (N - 1) / 2; k >= 0; --k) { sink(k,N); } while (N >= 1) { int temp = a[0]; a[0] = a[N]; a[N--] = temp; sink(0,N); } } public void display() { for (int i = 0; i < a.length; ++i) StdOut.print(a[i] + " "); StdOut.println(); } }