C#：TopK：1万个数取前最大的100，堆排序

1. 把1万个数字的前100个 首先放入数组，构成最小堆

1. 再循环100到一万之间的。 每次循环判断当前数字是否大于ary[0]
2. 当大于时，首先把头节点remove，再把当前数字放入ary[0]， 在那100个数之内进行最小堆排序
3. 当循环完循环100到一万后。 最大的前100个数字就出来了。

时间复杂度

第一次构建最小堆时，可以不堆排序，而是把最小值放入到头节点 例如：k为头100，n为1万 时间复杂度：O（k n*logk） 空间复杂度：O（n）

堆排序

代码语言：javascript复制

using System;
using System.Collections.Generic;
using System.Text;

namespace DataStructure
{
    public enum HeapType
    {
        MinHeap,
        MaxHeap
    }

    public class BinaryHeap<T> where T : IComparable<T>
    {
        public List<T> items;

        public HeapType HType { get; private set; }

        public T Root
        {
            get { return items[0]; }
        }

        public BinaryHeap(HeapType type)
        {
            items = new List<T>();
            this.HType = type;
        }

        public bool Contains(T data)
        {
            return items.Contains(data);
        }

        
        /// <summary>
        /// 插入尾部，再跟父节点冒泡排序
        /// </summary>
        /// <param name="item"></param>
        public void Push(T item)
        {
            items.Add(item); //先插入list的末尾

            int i = items.Count - 1;

            bool flag = HType == HeapType.MinHeap;

            while (i > 0)  //一直冒泡到头节点，当前节点的父节点idx为(i - 1) / 2
            {
                if ((items[i].CompareTo(items[(i - 1) / 2]) > 0) ^ flag) //异或，相同取0，相异取1；如果是子>父 异或 最小堆（true） == 0，不发生交换
                {
                    T temp = items[i];
                    items[i] = items[(i - 1) / 2];
                    items[(i - 1) / 2] = temp;
                    i = (i - 1) / 2;
                }
                else
                    break;
            }
        }

        /// <summary>
        /// 删除头节点
        /// </summary>
        private void DeleteRoot()
        {
            int i = items.Count - 1;

            items[0] = items[i]; //先把队尾部放入头节点
            items.RemoveAt(i);  //移除队尾

            i = 0;

            bool flag = HType == HeapType.MinHeap;

            while (true)
            {
                int leftInd = 2 * i   1; //左节点
                int rightInd = 2 * i   2;//右节点
                int largest = i;

                if (leftInd < items.Count)
                {
                    if ((items[leftInd].CompareTo(items[largest]) > 0) ^ flag) //（左 > 父） 异或（是否最小堆）
                        largest = leftInd;
                }

                if (rightInd < items.Count)
                {
                    if ((items[rightInd].CompareTo(items[largest]) > 0) ^ flag)
                        largest = rightInd;
                }

                if (largest != i) //发生交换，父与左或者右的一个
                {
                    T temp = items[largest];
                    items[largest] = items[i];
                    items[i] = temp;
                    i = largest;
                }
                else //未发生交换，说明排序OK
                    break;
            }
        }

        //弹出头节点
        public T PopRoot()
        {
            T result = items[0];

            DeleteRoot();

            return result;
        }

        public T GetRoot()
        {
            T result = items[0];
            return result;
        }
    }

}

TopK

代码语言：javascript复制

public class TestTopK : MonoBehaviour
{
    const int m_count = 10;
    const int m_top = 5;
    List<int> m_listOri = new List<int>(m_count);
    // Start is called before the first frame update
    void Start()
    {
        DataInit();

        BinaryHeap<Node> minHeap = new BinaryHeap<Node>(HeapType.MinHeap);
        
        for (int i = 0; i < m_top; i  )
        {
            minHeap.Push(new Node(m_listOri[i]));
        }

        for (int i = m_top; i < m_count; i  )
        {
            int topNum = minHeap.GetRoot().value;

            if (m_listOri[i] > topNum) //这里不能>=，因为是最小堆，只有大于头节点才插入，除头节点外，子节点都是比头节点大
            {
                minHeap.PopRoot();
                minHeap.Push(new Node(m_listOri[i]));
            }
        }
       
        for (int i = m_top-1; i >= 0 ; i--)
        {
            Debug.Log(minHeap.items[i].value);
        }
    }

    void DataInit()
    {

        //for (int i = 0; i < m_count; i  )
        //{
        //    int num = UnityEngine.Random.Range(0, m_count);
        //    m_listOri.Add(num);
        //}

        int[] buf = new int[m_count] { 5, 5, 1, 1, 9, 9, 2, 2, 3, 3 };
        m_listOri.AddRange(buf);
        
    }
}

测试输出

源码

https://github.com/luoyikun/UnityForTest TestTopK场景

c# int public 测试 数组

0 人点赞