堆（堆排序）---完全二叉树_构建堆 完全二叉树

堆

（一)堆
1、定义：堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

假设父亲的下标是parent
leftchild = parent * 2+1
rightchild = parent * 2+2

2、性质
a.堆中某个结点的值总是不大于或不小于其父结点的值；
b.堆总是一棵完全二叉树。
(二)分类
1、小根堆：父亲小于等于孩子
2、大根堆：父亲大于等于孩子

(三)实现堆排序（小堆）

void Swap(int* a,int* b)
{
	int tmp = *a;
	*a = *b;
	*b = 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 main()
{
	int a[] = {27,15,19,18,28,34,65,49,25,37};
	int n = sizeof(a)/sizeof(a[0]);
	ADJustDown(a,n,0);
	return 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

问题：左右子树不是小堆怎么办？

void Swap(int* a,int* b)
{
	int tmp = *a;
	*a = *b;
	*b = 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 main()
{
	int a[] = {15,18,28,34,65,19,49,25,37,27};//最大下标为n-1
	int n = sizeof(a)/sizeof(a[0]);
	//建堆
	for(int i = (n-1-1) / 2;i >= 0;i--)
		ADJustDown(a,n,0);
	return 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

#include<stdio.h>

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;
		}
	}
}

// 排升序，建大堆，还是小堆呢？-》大堆
void HeapSort(int* a, int n)
{
	// 建堆 -》 时间复杂度是多少？O(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;
	}
}

int main()
{

	int a[] = { 15, 18, 28, 34, 65, 19, 49, 25, 37, 27 };
	int n = sizeof(a) / sizeof(a[0]);
	HeapSort(a, n);

	return 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57