1.堆的概念及結構

如果有一個關鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存盤方式存盤
在一個一維陣列中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為
小堆(或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，

2.堆的性質：

堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，

3.堆的實作

typedef int HPDataType;
typedef struct Heap
{
 HPDataType* a;
 int size;
 int capacity;
}Heap;

（1）堆調整向下演算法

現在我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整成一個小堆，向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整，

int a[] = {27,15,19,18,28,34,65,49,25,37};

交換函式：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n) 
	{
		if (child + 1 < n && a[child + 1] > a[child]) 
		{
			++child;
		}

		if (a[child] > a[parent]) 
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else 
		{
			break;
		}
	}
}

（*）向下調整演算法時間復雜度

假設這個堆為滿二叉樹，堆高為h，假設每層高度為hi，假設每層結點數為ni，則建堆的時間復雜度為t(n)=Σni*hi,即：

（2）堆調整向上演算法

void AdjustUp(int* a, int n, int child)
{
	int parent = (child-1)/2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[parent], &a[child]);
			child=parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

（3）堆的創建

下面我們給出一個陣列，這個陣列邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現在我們通過演算法，把它構建成一個堆，根節點左右子樹不是堆，我們怎么調整呢？這里我們從倒數的第一個非葉子節點的子樹開始調整，一直調整到根節點的樹，就可以調整成堆，

int a[] = {1,5,3,8,7,6}; 

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	memcpy(hp->a, a, sizeof(HPDataType) * n);
	hp->size = n;
	hp->capacity = n;

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

（4）堆的銷毀

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->size = hp->capacity = 0;
}

（5）堆的插入

先插入一個80到陣列的尾上，再進行向上調整演算法，直到滿足堆，

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(hp->a, hp->size * 2 * sizeof(HPDataType));
		if (tmp == NULL)
		{
			printf("malloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity *= 2;
	}

	hp->a[hp->size - 1] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size, hp->size-1);
}

（6）堆的洗掉

洗掉堆是洗掉堆頂的資料，將堆頂的資料根最后一個資料一換，然后洗掉陣列最后一個資料，再進行向下調整演算法，

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size>0);
	Swap(&hp->a[0], &hp->a[hp->size-1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

（6）取堆頂的資料

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);
	return hp->a[0];
}

（7）堆的資料個數

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

（8）堆的判空

bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size==0;
}

（9）堆的列印

int HeapPrint(Heap* hp)//列印堆
{
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("/n");

	int num = 0;
	int leveSize = 1;
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
			num++;
		if (num == leveSize)
		{
			printf("\n");
			leveSize *= 2;
			num = 0;
		}
	}
}

（10）對陣列進行堆排序

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

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

4.堆的應用

（1）TopK問題

題目描述：

輸入整數陣列 arr ，找出其中最小的 k 個數

示例：

輸入：arr = [3,2,1], k = 2
輸出：[1,2] 或者 [2,1]

實作思路：

第一步：先取出陣列中的前K個資料，建大堆
第二步：依次剩下N-K個數，和堆頂的資料比較，如果比堆頂的資料小，則替換堆頂的資料，然后調整堆（向下調整法）
第三步：最后堆里的就是最小的K個數
時間復雜度：O(N*logK)
空間復雜度：O(K)

實作代碼：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n) 
    {
		if (child + 1 < n && a[child + 1] > a[child]) 
		{
			++child;
		}

		if (a[child] > a[parent]) 
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else 
		{
			break;
		}
	}
}


int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
    if(k==0)
    {
        *returnSize=0;
        return NULL;
    }

    int* arrRet=(int*)malloc(sizeof(int)*k);
    for(int i=0;i<k;i++)
    {
        arrRet[i]=arr[i];
    }

    for(int j=(k-1-1)/2;j>=0;j--)
    {
        AdjustDown(arrRet,k,j);
    }

    for(int i=k;i<arrSize;i++)
    {
        if(arr[i]<arrRet[0])
        {
            arrRet[0]=arr[i];
            AdjustDown(arrRet,k,0);
        }
    }
    *returnSize=k;
    return arrRet;
}