首页 > 程序开发 > 软件开发 > Java >

数据结构和算法学习三之Top K堆

2011-09-26

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

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

Java代码
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;
}
// swap
if (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(" ");
}

}

}

测试结果:
Java代码
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

作者“田麦夜月”

相关文章
最新文章
热点推荐