Top K堆实现

TOP K堆就是堆，只是TOP K堆只用维护固定数量的元素，每次加进来新的，都要判断是否替换掉堆顶元素，如果需要，则删除堆顶元素，放入新元素，并重新构造堆。可以参考这里

?

?

package com.kingdee.gmis.common;import java.util.Random;/** *  * @author hua_fan *  */public class TopNHeap<T extends Comparable<? super T>> {private int size;private int maxSize;private Object[] data = new Object[256];public TopNHeap(T[] data) {super();this.initHeap(data);}public TopNHeap(int fixedSize) {super();assert fixedSize >= 1;this.maxSize = fixedSize;}@SuppressWarnings("unchecked")public void initHeap(T[] data) {assert data.length >= 1;if (this.data.length <= this.size) {this.data = new Object[(int) (data.length * 1.5)];}this.maxSize = this.size = data.length;System.arraycopy(data, 0, this.data, 0, this.size);int startPos = this.getParentIndex(this.size - 1);for (int i = startPos; i >= 0; i--) {this.shiftdown(i);}}@SuppressWarnings("unchecked")public T getHeapTop() {return (T) this.data[0];}/** * 加元素到堆中，但是保持堆 的大小 *  * @param value */public void addToHeap(T value) {if (this.maxSize > this.size) {this.data[this.size] = value;this.shiftup(this.size++);} else {if (value.compareTo(this.getHeapTop()) > 0) {this.data[0] = value;this.shiftdown(0);}}}private void shiftup(int pos) {int parentIdx = this.getParentIndex(pos);while (pos != 0&& this.getValue(pos).compareTo(this.getValue(parentIdx)) < 0) {this.swap(pos, parentIdx);pos = parentIdx;parentIdx = this.getParentIndex(pos);}}public T removeTop() {T rst = this.getHeapTop();this.data[0] = this.data[--this.size];this.shiftdown(0);return rst;}public boolean hasNext() {return this.size > 0;}@SuppressWarnings("unchecked")public T[] getData() {return (T[]) this.data;}@SuppressWarnings("unchecked")public T getValue(int index) {return (T) this.data[index];}private int getParentIndex(int pos) {return (pos - 1) / 2;}private int getLeftChildIdx(int pos) {return pos * 2 + 1;}private int getRightChildIdx(int pos) {return pos * 2 + 2;}private void swap(int idx1, int idx2) {T tmp = this.getValue(idx1);this.data[idx1] = this.getValue(idx2);this.data[idx2] = tmp;}/** * 节点值向下级交换，构造堆 *  * @param pos */private void shiftdown(int pos) {int leftChildIdx = this.getLeftChildIdx(pos);// 没有子节点了if (leftChildIdx >= this.size) {return;}int rightChildIdx = getRightChildIdx(pos);int toBeSwapIdx = leftChildIdx;if (rightChildIdx < this.size&& this.getValue(leftChildIdx).compareTo(this.getValue(rightChildIdx)) > 0) {toBeSwapIdx = rightChildIdx;}// swapif (this.getValue(pos).compareTo(this.getValue(toBeSwapIdx)) > 0) {this.swap(pos, toBeSwapIdx);this.shiftdown(toBeSwapIdx);}}public boolean isFull(){return this.maxSize == this.size;}public int getMaxSize() {return maxSize;}/** * @param args */public static void main(String[] args) {Integer[] data = { 7, 12, 13, 24, 8, 6, 4, 27, 14, 8, 12, 56, 22 };TopNHeap<Integer> heap = new TopNHeap<Integer>(data);while (heap.hasNext()) {System.out.print(heap.removeTop());System.out.print("  ");}System.out.println("  ");heap.initHeap(data);for (int i = 0; i < 10; i++) {heap.addToHeap(i);}while (heap.hasNext()) {System.out.print(heap.removeTop());System.out.print("  ");}System.out.println("  ");heap = new TopNHeap<Integer>(10);Random rd = new Random();for (int i = 0; i < 20; i++) {int value = rd.nextInt(100);//System.out.print(value);//System.out.print("  ");heap.addToHeap(value);}System.out.println("  ");while (heap.hasNext()) {System.out.print(heap.removeTop());System.out.print("  ");}}}

测试结果：

?

4  6  7  8  8  12  12  13  14  22  24  27  56    7  8  8  8  9  12  12  13  14  22  24  27  56      60  61  64  65  67  67  71  74  74  97