二叉堆
堆排序
找流的中位数
public class BinHeap { long[] a; int size = 16; //数组大小 int count; //数据个数 boolean isMax; //是否是大根堆 public BinHeap() { a = new long[size]; } public BinHeap(int size, boolean isMax) { this.size = size; this.isMax = isMax; a = new long[size]; } public void add(long k) { reSize(); a[count + 1] = k; count++; swimUp(count); } //动态扩容 private void reSize() { if (count < size - 1) return; long[] a2 = new long[size << 1]; System.arraycopy(a, 0, a2, 0, a.length); a = a2; size <<= 1; } public long pop() { if (count > 0) { long n = a[1]; a[1] = a[count]; count--; sinkDown(1); return n; } throw new RuntimeException("null heap"); } public boolean isEmpty() { return count == 0; } public long top() { if (count > 0) return a[1]; throw new RuntimeException("null heap"); } public int getCount() { return count; } private void swimUp(int i) { long tmp = a[i]; int c = i; int p = i; for (; (c >> 1) > 0 && isMax ? (a[c >> 1] < tmp) : (a[c >> 1] > tmp); c = p) { p = c >> 1; a[c] = a[p]; //空节点上移, child = parent } a[p] = tmp; //填充空节点 } private void sinkDown(int i) { long tmp = a[i]; int p = i; int lc, rc, tc = i; //left child, right child, target child //TODO SUCK CODE! for (; p < (count / 2 + 1); p = tc) { lc = p << 1; rc = lc + 1; int tmptc; if (isMax) { if (rc > count) { if (a[lc] < tmp) { a[p] = a[lc]; tc = lc; } } else { tmptc = a[lc] < a[rc] ? rc : lc; if (a[tmptc] > tmp) { a[p] = a[tmptc]; tc = tmptc; } } } else { if (rc > count) { if (a[lc] < tmp) { a[p] = a[lc]; tc = lc; } } else { tmptc = a[lc] > a[rc] ? rc : lc; if (a[tmptc] < tmp) { a[p] = a[tmptc]; tc = tmptc; } } } if(p == tc) break; } a[tc] = tmp; } }
找数据流中的中位数
public class CenterNumber { // odd round even round // / // / // (small) - ------------o------------> + (big) stream numbers // max heap /^ min heap // small numbers / | big numbers // center number /** * 1.2个堆数量差 最大相差1 * 2.最后结束时，maxHeap中所有数 都小于 minHeap中所有数, 此时maxHeap的堆顶，或minHeap的堆顶为中位数 * 数据量为偶数个时（先从右边开始放入， minHeap),下一个数据时，放左边，依次交替 * * @param a */ BinHeap maxHeap; BinHeap minHeap; public void insertNum(long num) { //1 先满足数值大小，放入正确的堆 //2 再满足堆数量平衡 //2者不可弄反，否则堆数量平衡了，但最后求不到中位数 if (((minHeap.getCount() + maxHeap.getCount()) & 1) > 0) { //奇数,默认加到 maxHeap ，左边 , 用 > 或 < 比 == 判断往往所需cpu机器周期数更少，速度更快 if (!minHeap.isEmpty() && minHeap.top() < num) { //先判断，如果这个数比 右边 minHeap 中的最小还要大，就放到minHeap (右边） minHeap.add(num); num = minHeap.pop(); //平衡数量 } maxHeap.add(num); //左边 } else { //偶数,默认加到 minHeap ，右边 if (!maxHeap.isEmpty() && maxHeap.top() > num) { maxHeap.add(num); num = maxHeap.pop(); //平衡数量 } minHeap.add(num); //右边 } } public float getMidNum() { long dataCount = minHeap.getCount() + maxHeap.getCount(); if (dataCount > 0) { if ((dataCount & 1) > 0) //奇数个数据量，从minHeap中取得 return minHeap.top(); return (maxHeap.top() + minHeap.top()) / 2f; //偶数个数据量，2个中位数的平均数 } return 0; } //从数据流中获取中位数 public float centerNum(int[] datas) { maxHeap = new BinHeap(datas.length / 2 + 2, true); minHeap = new BinHeap(datas.length / 2 + 2, false); int c = 0; while (c < datas.length) { insertNum(datas[c++]); } return getMidNum(); } public static void main(String[] args) { CenterNumber cn = new CenterNumber(); int[] a = new int[]{ 1, 3, 4, 6, 5, 2 }; float mid = cn.centerNum(a); System.out.println(" mid " + mid); //3.5 a = new int[]{ 1, 3, 4, 6, 5, 2, 7 }; mid = cn.centerNum(a); System.out.println(" mid " + mid); //4 } }
基于堆的优先队列的任务定时器
public class TaskTimer { BinHeap priorityQueue = new BinHeap(); //PriorityBlockingQueue public interface TaskChangeSubscriber { void onGetNextTask(long time); void onTask(long time); } TaskChangeSubscriber taskChangeSubscriber; Thread workThread; public class TaskCheck implements Runnable { AtomicBoolean doRun = new AtomicBoolean(true); @Override public void run() { while (doRun.get()) { if (priorityQueue.getCount() > 0) { //PriorityBlockingQueue try { if (taskChangeSubscriber != null) taskChangeSubscriber.onGetNextTask(priorityQueue.top()); Thread.sleep(priorityQueue.top() - System.currentTimeMillis()); if (priorityQueue.top() - System.currentTimeMillis() <= 0 && taskChangeSubscriber != null) { taskChangeSubscriber.onTask(priorityQueue.pop()); } } catch (InterruptedException e) { e.printStackTrace(); } } } } } TaskCheck taskCheck; public TaskTimer() { } public void start() { if (workThread != null) { taskCheck.doRun.set(false); } taskCheck = new TaskCheck(); workThread = new Thread(taskCheck); workThread.start(); } public void stop() { if (workThread != null) { taskCheck.doRun.set(false); } taskCheck = null; workThread = null; } public void addTask(long time) { System.out.println("addTask : " + time); priorityQueue.add(time); } //取消任务？ 堆的删除算法? public TaskChangeSubscriber getTaskChangeSubscriber() { return taskChangeSubscriber; } public void setTaskChangeSubscriber(TaskChangeSubscriber taskChangeSubscriber) { this.taskChangeSubscriber = taskChangeSubscriber; } public static void main(String[] args) throws InterruptedException { TaskTimer t = new TaskTimer(); t.setTaskChangeSubscriber(new TaskChangeSubscriber() { @Override public void onGetNextTask(long time) { System.out.println("TaskTimer.onGetNextTask " + time); } @Override public void onTask(long time) { System.out.println("TaskTimer.onTask " + time); } }); t.addTask(System.currentTimeMillis() + 3000); t.start(); Thread.sleep(3000*2); t.addTask(System.currentTimeMillis() + 3000); Thread.sleep(1500); t.addTask(System.currentTimeMillis() + 3000); } }
TopK 问题是一个只有 右侧 minHeap 的中位数问题
同理 LowK 只有左侧 MaxHeap