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

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).compar

补充：软件开发 , Java ,