5.3二叉树

    承接上一篇博客的优化堆排序HeapSort

    //堆数组建堆有两种方法
    //1.使用向上调整，插入数据的思想
    //2.使用向下调整，插入数据的思想
    
    //向下调整有要求:左右子树不能为小堆
    
    void HeapSort(int* a, int size)
    {
    	//向上调整---建堆
    	//时间复杂度O(N*logN)
    	for (int i = 1; i < size; ++size)
    	{
    		AdjustUp(a, i);
    	}
    }
    
    void HeapSort1(int* a, int size)
    {
    	//向下调整---建堆
    	//时间复杂度O(N)
    	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDown(a, size, i);
    	}
    }
    
    //TOP-K问题 N个数找出最大/最小的前K个
    //方法:
    //1.排序---时间复杂度:O(N*logN) 空间复杂度:O(1)---要进一步优化
    //2.建立N个数的大堆，HeapPop K次，就可以选出最大的前K个 时间复杂度:O(N+logN*K) 空间复杂度O(1)
    
    //TOP-K问题一般用来处理N比较大的数据问题
    //但是有可能N非常大，以及远大于K
    //比如100亿个数里面找出最大的前10个
    //以上方法两个方法就不能用了 因为内存不够用来建立堆
    
    //求解思维:
    //用前K个数建立一个K个数的小堆，然后剩下的N-K个依次遍历
    //如果比堆顶的数据大，就替换它进堆，最后堆里面的K个数就是
    //最大的K个数
    
    //时间复杂度：O(K+logK*(N-K)) 空间复杂度O(1)
    
    
    //代码实现：
    void PrintTopK(int* a, int n, int k)
    {
    	// 1. 建堆--用a中前k个元素建堆
    	int* kminHeap = (int*)malloc(sizeof(int) * k);
    	assert(kminHeap);
    	for (int i = 0; i < k; i++)
    	{
    		kminHeap = a[i];
    	}
    	//建立小堆
    	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
    	{
    		AdjustDown(kminHeap, k, j);
    	}
    	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
    	for (int i = k; i < size; ++i)
    	{
    		if (a[i] > kminHeap[0])
    		{
    			kminHeap[0] = a[i];
    			AdjustDown(kminHeap, k, 0);
    
    		}
    	}
    	for (int j = 0; j < k; j++)
    	{
    		printf("%d ", kminHeap[j]);
    	}
    	printf("n");
    	free(kminHeap);
    }
    void TestTopk()
    {
    	int n = 10000;
    	int* a = (int*)malloc(sizeof(int) * n);
    	srand(time(0));
    	for (size_t i = 0; i < n; ++i)
    	{
    		a[i] = rand() % 1000000;
    	}
    	a[5] = 1000000 + 1;
    	a[1231] = 1000000 + 2;
    	a[531] = 1000000 + 3;
    	a[5121] = 1000000 + 4;
    	a[115] = 1000000 + 5;
    	a[2335] = 1000000 + 6;
    	a[9999] = 1000000 + 7;
    	a[76] = 1000000 + 8;
    	a[423] = 1000000 + 9;
    	a[3144] = 1000000 + 10;
    	PrintTopK(int* a, n, 10);
    }