建堆的时间复杂度、topk问题

前言

本篇旨在介绍使用向上调整建堆与向下调整建堆的时间复杂度. 以及topk问题

堆的时间复杂度

建堆的时间复杂度

向下调整法建堆

// 堆的插入
void HeapPush(Heap* hp, HPDataType x) {
	assert(hp);
    //与顺序表的开辟类似
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
        //使用三目操作符开辟空间大小
		HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
 
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->size++;
	hp->a[hp->size] = x;
//向下调整法，因为每次的插入是在数组末尾
//每次插入需要与父亲比较大小交换
	AdjustUp(hp->a, hp->size - 1);
}

 因此：建堆的时间复杂度为O(N)。

等比数列求和公式： 
建堆要从倒数第一个非叶子节点开始调整，也即是从倒数第二层开始调，可得出时间复杂度公式：T ( n ) = ∑ ( 每 层 节 点 数 ∗ ( 堆 的 高 度 − 当 前 层 数 ) ) 
建堆的时间复杂度为O(N)。（向下调整算法）

为何使用向下调整建堆而不使用向上调整建堆

向上调整法建堆

可以看出结点数多的层, 调整次数也多, 结点数少的层, 调整次数少, 时间复杂度为O(N*logN), 所以一般建堆都采用向下调整建堆法.

TOPK问题

TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。

比如：专业前十、世界500强、销量最高的前十、富豪榜等等

 我们常常会想到冒泡排序( O(N^2) )
对于少量的数据是可以拿捏的，但面对100000的数据就显得有点吃力，而堆排序O(N*logN)则觉得轻而易举

堆排序 

void HeapSort(int* a, int n)
{
	// 降序，建小堆
	// 升序，建大堆
	// 向上调整建堆 O(N*logN)
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	// 向下调整建堆 O(N)
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}