初级数据结构--堆

• 1. 堆的两种状态：
• 2. 特殊情况：除了根节点以外，左子树右子树都是大堆或者小堆。
• 3. 堆数组的下标：
• 4. 建堆：给一个数组，转换成堆，大堆或小堆
• 5. 对一个数组，排升序要建大堆；排降序要建小堆
• 6. 证明建堆的时间复杂度：O(N)
• 8. 插入堆，保持继续是堆
• 9. 删除堆顶数据，保持继续是堆
• 12. TOP K问题

1. 小根堆
	-  所有的双亲结点都比孩子节点小，孩子节点都比双亲结点大
2. 大根堆
	- 所有的双亲结点都比孩子节点大，孩子节点都比双亲结点小

- 堆向下调整算法
- 从根开始，不断往下交换
- 选出孩子中间最小的，和双亲结点比较：：
- 比双亲结点小，与其交换，双亲变孩子，孩子变双亲，从孩子结点继续往下比较，交换，最坏调到叶子终止
- 比双亲结点大，则终止
- 算法的时间复杂度：
- 一个需要交换高度次，N个结点是：N倍的logN。

/ 条件：左右子树都是小堆
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;
		}

		/ 1、如果小孩子比父亲小，则交换，继续往下调整
		/ 2、如果小的孩子比父亲大，则结束调整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

- 左孩子的下标是，双亲结点的二倍加一；
- 右孩子的下标是，双亲结点的二倍加二；
- 右孩子的下标是，左孩子下标加一；
- 已知孩子结点下标，双亲结点下标是，该坐标减去一，除以2；

- 找到最后一个非叶子节点的父节点，调用向下调整算法
- 然后开始调整每一个分支节点，直至到0；
- 最后一个非叶子结点的坐标是：数组的最后一个，数组的大小减一

i:最后一个叶子结点是 n-1 ，套用关系，则父节点是 n-1-1  / 2 
	for ( int i = (n-1-1)/2; i>=0;--i)
	{
		AdjustDown(a, n, i);
	}

• 根是最大的数，交换放到数组最后，数组长度减一；
• 原堆结构不变，调用向下调整算法，可以得出第二大，再次放到数组最后，数组长度减一；
• 数组下标 i = 0时停止…

// O(N*logN)
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;
	}
}

• 将堆视为满二叉树来计算：每一层的结点个数，乘以，每个节点最坏向下调整的层数
• 最后一层不用动，加到第H–1层.

void HeapPush(HP* php, HeapDaT x)
{
	assert(php);
	不够扩容
	if (php->cap == php->size)
	{
		int newcap = php->cap == 0 ? 5 : 2 * php->cap;
		php->a = (HeapDaT*)realloc(php->a,newcap * sizeof(HeapDaT));
		php->cap = newcap;
	}
		php->a[php->size] = x;
		php->size++;
在尾部插入，只需比较他父结点的那一条路径，
	AdjustUp(php->a, php->size - 1);
}

堆顶数据和数组尾部数据换一下，调用向下调整，数组长度减一即可
void HeapPop(HP* php)
{
	assert(php);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

选出N个数中，前K个最大的数

建立一个K个数的小堆，有比堆顶数大的就进堆，最后便是K个最大的数

void 	TOpK()
{

	
	int k = 5;
	int a[100] = { 0 };
	//for (int i = 0; i < 10; i++)
	//{
	//	a[i] = rand();
	//}
	a[50] = 199;
	a[60] = 990;
	a[72] = 699;
	a[32] = 799;
	a[24] = 899;
	HP hp;
	HeapInit(&hp, a, 5);
	int i = 0;
	for ( i = 5; i < 100; i++)
	{
		if (a[i]>HeapTop(&hp))
		{
		外部数据比堆顶小，则入堆，pop和push 会继续保持堆有序
			HeapPop(&hp);
			HeapPush(&hp,a[i]);
		}
	}
	HeapPrint(&hp);
	HeaDestory(&hp);
}

某一天的人人影视…