C ＃: TOPK: take the largest 100 before 10000 numbers, and sort the heap

1. hold 1 The first ten thousand digits 100 individual First put the array , Make up the smallest heap
2. recycling 100 Between... And 10000 . Each cycle determines whether the current number is greater than ary[0]
3. When greater than , First, put the head node remove, Then put the current number into ary[0], There 100 Minimum heap sort within the number
4. When the cycle is over 100 After ten thousand . The biggest front 100 A number comes out .

Time complexity

The first time you build the smallest heap , Heap sorting is not allowed , Instead, put the minimum value into the head node
for example ：k For the head 100,n by 1 ten thousand
Time complexity ：O（k+n*logk） Spatial complexity ：O（n）

Heap sort

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>
        ///  Insert the tail , Then bubble sort with the parent node 
        /// </summary>
        /// <param name="item"></param>
        public void Push(T item)
        {
    
            items.Add(item); // First insert list At the end of 

            int i = items.Count - 1;

            bool flag = HType == HeapType.MinHeap;

            while (i > 0)  // Bubbling all the way to the head node , Parent of current node idx by (i - 1) / 2
            {
    
                if ((items[i].CompareTo(items[(i - 1) / 2]) > 0) ^ flag) // Exclusive or , Take the same 0, Different take 1; If it's Zi > Father   Exclusive or   The smallest pile （true） == 0, There is no exchange 
                {
    
                    T temp = items[i];
                    items[i] = items[(i - 1) / 2];
                    items[(i - 1) / 2] = temp;
                    i = (i - 1) / 2;
                }
                else
                    break;
            }
        }

        /// <summary>
        ///  Delete header node 
        /// </summary>
        private void DeleteRoot()
        {
    
            int i = items.Count - 1;

            items[0] = items[i]; // First put the tail of the team into the head node 
            items.RemoveAt(i);  // Remove the tail 

            i = 0;

            bool flag = HType == HeapType.MinHeap;

            while (true)
            {
    
                int leftInd = 2 * i + 1; // The left node 
                int rightInd = 2 * i + 2;// Right node 
                int largest = i;

                if (leftInd < items.Count)
                {
    
                    if ((items[leftInd].CompareTo(items[largest]) > 0) ^ flag) //（ Left  >  Father ）  Exclusive or （ Whether the minimum heap ）
                        largest = leftInd;
                }

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

                if (largest != i) // Swapping occurs , Father and left or right one 
                {
    
                    T temp = items[largest];
                    items[largest] = items[i];
                    items[i] = temp;
                    i = largest;
                }
                else // There was no exchange , Description sorting OK
                    break;
            }
        }

        // Pop out the head node 
        public T PopRoot()
        {
    
            T result = items[0];

            DeleteRoot();

            return result;
        }

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

}

TopK

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) // There's no way to >=, Because it's the smallest pile , Only nodes larger than the head are inserted , Except for the head node , The child nodes are larger than the head node 
            {
    
                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);
        
    }
}

Test output

Source code

https://github.com/luoyikun/UnityForTest
TestTopK scene