무질서 한 배열 에서 최소 M 개의 요 소 를 가 져 옵 니 다.

제 동창 인 대 룡 이 저 에 게 알고리즘 문 제 를 주 었 습 니 다. 길이 가 N 인 무질서 한 배열 을 정 하고 그 중에서 가장 작은 M 개 수 (M < = N) 를 어떻게 선택 합 니까?나의 첫 번 째 생각 은 전체 배열 을 빠 른 정렬 로 정렬 한 다음 에 정렬 된 배열 을 옮 겨 다 니 며 그 중에서 M 개의 가장 작은 수 를 선택 하 는 것 이다.비록 이 방법 은 실행 할 수 있 지만, 가장 좋 은 것 은 아니다.쌓 아 올 리 는 사상 으로 이 문 제 를 잘 해결 할 수 있다.작은 지붕 더 미 를 만 들 고 맨 위 에 있 는 최소 요 소 를 던 질 때마다 M 번 을 순환 하면 최소 M 개 수 를 얻 을 수 있 습 니 다.이 알고리즘 문 제 는 쌓 아 올 리 는 정렬 의 응용 이 라 고 볼 수 있다.
정렬 알고리즘 을 쌓 으 려 면 제 다른 글 을 보 세 요.http://www.cnblogs.com/mingmingruyuedlut/archive/2011/09/13/2175308.html
구체 적 인 코드 는 다음 과 같다.

 /// <summary>
        ///          N（count）     
        /// </summary>
        /// <param name="array">       </param>
        /// <param name="count">  count     </param>
        private static void GetSmallerNumbers(int[] array, int count)
        {
            BuildMinHeap(array);    //     
            for (int i = array.Length - 1; i >= array.Length - count; i--)  //     
            {
                Console.WriteLine(array[0]);    //         （ ：        ）
                Swap(ref array[0], ref array[i]);   //                    
                MinHeapify(array, 0, i);    //        
            }
        }

        /// <summary>
        ///      
        /// </summary>
        /// <param name="array">     </param>
        private static void BuildMinHeap(int[] array)
        {
            //           ：    0 ~ array.Length / 2 - 1          ，         
            for (int i = array.Length / 2 - 1; i >= 0; i--)
            {
                MinHeapify(array, i, array.Length); //      
            }
        }

        /// <summary>
        ///     ：        
        /// </summary>
        /// <param name="array">     </param>
        /// <param name="currentIndex">          </param>
        /// <param name="heapSize">        （ ：               ）</param>
        private static void MinHeapify(int[] array, int currentIndex, int heapSize)
        {
            int leftChildIndex = currentIndex * 2 + 1;  //           
            int rightChildIndex = currentIndex * 2 + 2; //           
            int smallestIndex = currentIndex;   //  （   、    、    ）         
            if (leftChildIndex < heapSize && array[leftChildIndex] < array[smallestIndex])
            {
                smallestIndex = leftChildIndex;
            }
            if (rightChildIndex < heapSize && array[rightChildIndex] < array[smallestIndex])
            {
                smallestIndex = rightChildIndex;
            }
            if (smallestIndex != currentIndex)  //                  
            {
                Swap(ref array[currentIndex], ref array[smallestIndex]);
                MinHeapify(array, smallestIndex, array.Length); //    
            }
        }

        /// <summary>
        ///     
        /// </summary>
        /// <param name="a">  a</param>
        /// <param name="b">  b</param>
        private static void Swap(ref int a, ref int b)
        {
            int temp = 0;
            temp = a;
            a = b;
            b = temp;
        }

。。。。