建堆（堆化）与堆排的时间复杂度和空间复杂度的推导及TopK问题

一：建堆
第一种情况：时间复杂度O（logn）
若左右子树恰好都是小堆，如何建小堆呢？

算法：向下调整算法
1.

	选出孩子中小的那一个

a）小的孩子跟父亲相比，比父亲小则与父亲交换，并把原来孩子的位置当成父亲的新位置继续往下调整，直到
parent走到叶子节点
b）若比父亲大则不需要处理，调整完成，整个树已经是小堆。

//向下调整算法

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (a[child] > a[child + 1] && child + 1 < n)  //建小堆
		//if (a[child] < a[child + 1] && child + 1 < n)  //建大堆
		{
			child++;
		}
		if (a[child] < a[parent])	//小堆
		//if (a[child] > a[parent]) //大堆
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}

第二种情况：左右子树不是小堆，怎么办？
时间复杂度O(n)

从倒数第一个非叶子结点开始，从后往前按编号，依次作为子树去向下调整。

n表示结点个数，n-1表示最后一个叶子节点的下标，由于child = 2*parent+1，所以最后一个非叶子结点的下标是(n-1-1)/2。

	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

建堆的时间复杂度O(n)
推导过程：
假设高度为k，则从倒数第一个非叶子节点（最后一个叶子节点的父节点）开始，从后往前按编号，依次进行向下调整。
那么第i层所花的最坏的时间是s = 2^(i-1)*(k-i);
由于叶子层不用交换所以i从k-1层开始到1；
因此总时间S = 2^(k-2) * 1 + 2^(k-3) * 2…+2 (k-2)+2⁽⁰⁾ * (k-1)
利用高中所学知识错位相减法得出
S = 2^(k-1) + 2^(k-2) + 2 ^(k-3)+ … + 2¹ +2⁰ * (k-1)

按最坏的来算：k=logn。此时S = n-logn-1
所以建堆的时间复杂度为O(n)

堆排(nlogn)

void heapsort(int* a, int n)/
void Swap(int* a,int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void AdjustDown(int* min_arr, int n,int parent)
{
    int child = 2*parent+1;
    while(childmin_arr[parent])//大堆
        {
            Swap(&min_arr[child],&min_arr[parent]);
            parent = child;
            child = 2*parent+1;
        }
        else
            break;
    }
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
        if(k == 0)
        {
            *returnSize = 0;
            return NULL;
        }
        int* min_arr = (int*)malloc(sizeof(int)*k);
        
        for(int i = 0;i= 0; --j)
        {
            AdjustDown(min_arr,k,j);
        }

        //维护堆，若arr数组中剩下的数小于堆顶的数则进行交换，同时向下调整
        for(int i = k;iarr[i])
            {
                min_arr[0] = arr[i];
                AdjustDown(min_arr,k,0);
            }
        }
        *returnSize = k;
        return min_arr;
}