从无序数组中获取最小的M个元素(小顶堆实现)

2019/7/23 1:54:04 人评论 次浏览 分类:学习教程

原文链接:http://www.cnblogs.com/mingmingruyuedlut/archive/2011/09/20/2182431.html

我同学大龙给我出了一道算法题:给定一个长度为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;
}

。。。。

转载于:https://www.cnblogs.com/mingmingruyuedlut/archive/2011/09/20/2182431.html

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->