欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆的应用

程序员文章站 2024-03-15 21:47:54
...

关于堆的概念以及堆的创建、删除、插入可以戳这里~

                            https://blog.csdn.net/Z_JUAN1/article/details/80954426

 

一、100亿个数中找出最大的前k个数(海量top k 的问题)

        分析:

                1.首先我们需要建堆,那么是大堆还是小堆?由于要找的是最大的前k个数,那么我们选择建小堆

                2.如何建?我们将前k个数进行建堆,此时堆顶的元素就是最小的,用后面的数逐个和堆顶元素比较,若比小堆的堆顶 元素还小,那么堆保持不变,若比堆顶元素大,那么就替换堆顶元素,再次进行调整,使其满足堆的性质。

                3.找最小的数就是正好相反。

代码如下~

//建小堆
void AdjustArrayDown(int array[], int size, int parent)
{
	int left, right,min;
	while (1) {
		left = parent * 2 + 1;
		right = parent * 2 + 2;
		if (left >= size) {
			return;
		}
		min = left;
		if (right < size && array[right] < array[left]) {   
			min = right;
		}

		if (array[parent] <= array[min]) {
			return;
		}
		swap(array + parent, array + min);
		parent = min;
	}
}

//找出最大的数
int *TopK(int array[], int size, int k)
{
	int i;
	int *rarray = (int *)malloc(sizeof(int)*k);
	for (i = 0; i < k; i++)  
	{
		rarray[i] = array[i];   //先将前k个数放到rarry中
	}
	//建堆rarray
	for (i = k - 2 / 2; i >= 0; i--){
		AdjustArrayDown(rarray, k, i);    //对前k个数进行建小堆
	}
	for (i = k; i < size; i++)
	{
		if (array[i] > rarray[0])   //只要比最小堆的堆的顶大,就进行替换
			rarray[0] = array[i];
		AdjustArrayDown(rarray, k, 0);
	}
	return rarray;
}

堆的应用

二、堆排序(从小到大)

         分析

                1.建大堆还是小堆?

                         建小堆:我们建一次就会得到堆顶是最小的,下一次我们依然得通过建堆的方式得到下一个元素,这么下来,我们需要建size-1次的堆

                        建大堆:我们建一次的到最大的数,使第一个元素和最后一个元素交换位置,我们就得到了最大的那个元素,使size-1,在进行向下调整,得到下一个元素,此时我们建堆只需要建一次

                2.综上考虑,我们选择建大堆

        代码~

建大堆的代码可以进文章开头链接里的文章获得哦~

//排序
void heapSort(int array[], int size)
{
	int i;
	for (i = size / 2 - 1; i >= 0; i--)
	{
		AdjustArrayDown(array, size, i);
	}
	for (i = 0; i < size; i++){
		swap(&(array[0]), &(array[size - 1-i]));
		AdjustArrayDown(array, size - 1 - i, 0);
	}
}

堆的应用

以上堆的两个应用特别广泛

尤其第一个,比如我们淘宝的时候可以进行选择价格由低到高或由高到低

 

 

相关标签: 堆的应用