学步园

我同学大龙给我出了一道算法题：给定一个长度为N无序的数组，怎么从中挑选出最小的M个数（M<=N）?
我的第一想法就是用快速排序将整个数组进行排序，然后遍历排序后的数组，从中选处M个最小的数。虽然这个方法可行，但是不是最好的。
用堆排序的思想就可以很好的解决这个问题。创建小顶堆，然后每次将堆顶最小元素抛出，循环M次即可获取最小的M个数。

这个算法题也可以认为是堆排序的一个应用。

 /// <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;
        }