数据结构：“大根堆、小根堆”的向上调整算法和向下调整算法_大根堆向上调整从哪个节点开始

堆

堆是一种特殊的完全二叉树。
堆有两种类型：大根堆和小根堆。

例1中的完全二叉树符合所有父亲节点的数据小于其孩子节点的，故为小根堆；

例2中的完全二叉树符合所有父亲节点的数据大于其孩子节点的，故为大根堆。

如果给你一个完全二叉树，需要将这个二叉树调整为堆，你会怎么做？
这个时候最好的方法便是调整算法。

【向上调整算法】

【向下调整算法】
与向上调整法有些不一致，这就像一个父亲有两个孩子，过年的时候，如果孩子们想去父亲家，只有一个去处，而换做父亲，该去哪个孩子家过年呢？很多家庭都偏爱小的，所以父亲选择去小儿子家过年。

在向下调整的时候与偏小的孩子节点之间进行调整。

向上调整算法和向下调整算法最能体现在堆的插入和删除

typedef struct Heap
{
	HeapDataType* a;
	int size;
	int capacity;
}HP;
1
2
3
4
5
6

【堆的插入】

先将要插入的元素插入到堆的末尾，插入后如果堆的性质被破坏，将新插入的节点顺着其父亲节点往上重新调整为堆。

void AdjustUp(int* a, int child)
{
	assert(a);
     //父亲节点的下标
	int parent = (child - 1) / 2;
	
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
		    //交换
			Swap(&a[child], &a[parent]);
            //迭代
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
	    //如果容量为0则开四个整形空间，如果不喂0开它原来的两倍
		size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType)*newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		hp->a = tmp;
		hp->capacity = newCapacity;
	}

	hp->a[hp->size] = x;
	hp->size++;

    //重新调整为堆
	AdjustUp(hp->a, hp->size - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

【堆的删除】

1.将堆顶的元素与堆中原本的最后一个元素进行交换
2.删除堆中的最后一个元素
3.将堆顶的元素向下调整直到满足堆的特性为止。

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[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 删除堆顶的数据
void HeapPop(HP* hp)
{
	assert(hp);
	if（hp->size == 0）
	{
	   printf("pop fail\n");
	   exit(-1);
	}
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

	AdjustDown(hp->a, hp->size, 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---