//最小堆（二叉树的一种）
class Dui
{
    public int[] datas;

    public Dui(int maxLength) {
        if (maxLength <= 0)
        {
            datas = new int[16 + 1];
        }
        else {
            datas = new int[maxLength + 1];
        }
    }

    public void CompareAndReplace(int data) {
        if (data > datas[1]) {
            datas[1] = data;
            SiftDown(1);
        }
    }

    //向下调整
    public void SiftDown(int index) {
        bool isNeedSwap = true;
        int t = index;
            
        //有左儿子
        while (index * 2 <= datas[0] && isNeedSwap) {
            if (datas[index] > datas[index * 2]) {
                t = index * 2;
            }

            //有右儿子
            if (index * 2 + 1 <= datas[0]) {
                if (datas[t] > datas[index * 2 + 1]) {
                    t = index * 2 + 1;
                }
            }

            if (index != t)
            {
                int temp = datas[index];
                datas[index] = datas[t];
                datas[t] = temp;
                index = t;
            }
            else {
                //比左右两儿子都小了
                isNeedSwap = false;
            }
        }
    }

    public void Insert(int val) {
        if (datas.Length - 1 == datas[0]) {
            //我这里就不重构数组了
            Console.WriteLine("最小堆已满!");
            return;
        }

        int insertIndex = datas[0] + 1;
        datas[insertIndex] = val;
        datas[0]++;
        SiftUp(insertIndex);
    }
    
    public override string ToString() {
        string ss = "";
        for (int i = 1; i <= datas[0]; i++) {
            ss += i+":" + datas[i] + "  ";
        }

        return ss;
    }
}

static void Main(string[] args)
{
    Dui dui = new Dui(3);
    int[] datas = { 10, 5, 3, 99, 1, 5, 6, 20, 7, 33 };
    dui.Insert(datas[0]);
    dui.Insert(datas[1]);
    dui.Insert(datas[2]);
    for (int i = 3; i < datas.Length; i++) {
        dui.CompareAndReplace(datas[i]);
    }
    Console.WriteLine(dui);
    Console.ReadKey();
}

利用最小堆根节点的元素为堆中的最小值，先生成一个只有3个元素的堆（假如找前三大的），随机初始化，然后一一比较要寻找的数据和根节点，只要比根节点小的，都不是第三大的数值，如果比根节点数据大，这才舍弃根节点数据替换为当前比较数值，再向下调整，继续比较。