数据结构-堆的实现_数据结构偶堆的实现

堆的实现

Heap.h 堆的管理及接口

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

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

//堆的向下调整算法
void AdjustDown(HPDataType* a, int n, int root);
//堆的向上调整算法
void AdjustUp(HPDataType* a, int child);
//堆的初始化
void HeapInit(Heap* php, HPDataType* a,int n);
//堆的销毁
void HeapDestroy(Heap* php);
//堆的插入
void HeapPush(Heap* php, HPDataType x);
//堆的删除
void HeapPop(Heap* php);
//堆里的数据个数
int HeapSize(Heap* php);
//判断堆是否为空
int HeapEmpty(Heap* php);
//取堆顶数据
HPDataType HeapTop(Heap* php);
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

Heap.c 堆各个接口功能的实现

• 堆的插入：将x插入下标为size的位置，++size然后使用向上调整算法调整
• 堆的删除(删栈顶数据)：将栈顶数据和下标为size-1位置的数据交换，然后–size,使用向下调整算法调整

#include "Heap.h"

//堆向下调整算法
//建小堆
void AdjustDown(HPDataType* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	//孩子超过数组下标结束
	while (child < n)
	{
		//child始终左右孩子中小的那个
		if (a[child + 1] < a[child] && child + 1 <n)//防止没有右孩子
		{
			++child;
		}
		//小的往上浮，大的往下沉
		if (a[child] < a[parent])
		{
			int tem = a[parent];
			a[parent] = a[child];
			a[child] = tem;
			parent = child;
			child = parent * 2 + 1;
		}
		//中途child>parent则已满足小堆，直接break
		else
		{
			break;
		}
	}
}
//堆的向上调整算法
//建小堆
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			int tem = a[parent];
			a[parent] = a[child];
			a[child] = tem;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//堆的初始化
void HeapInit(Heap* php, HPDataType* a, int n)
{
	assert(php);
	assert(a);
	php->a = (HPDataType*)malloc(n * sizeof(HPDataType));
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	for (int i = 0; i < n; i++)
	{
		php->a[i] = a[i];
	}
	//建堆
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(php->a, n, i);
	}
	php->capacity = n;
	php->size = n;
}
//堆的销毁
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}
//堆的插入
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tem = (HPDataType*)realloc(php->a,php->capacity * 2 * sizeof(HPDataType));
		if (tem == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tem;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	++php->size;
	AdjustUp(php->a,php->size - 1);
}
//堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	HPDataType tem = php->a[php->size - 1];
	php->a[php->size - 1] = php->a[0];
	php->a[0] = tem;
	--php->size;
	AdjustDown(php->a, php->size, 0);
}
//堆里的数据个数
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}
//判断堆是否为空
//为空返回1，不为空返回0
int HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0 ? 1 : 0;
}
//取堆顶数据
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

test.c测试

#include "Heap.h"

void TestHeap()
{
	int arr[] = { 27, 28, 65, 25, 15, 34, 19, 49, 18, 37 };
	Heap hp;
	HeapInit(&hp, arr, sizeof(arr)/sizeof(int));
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);

	}
	printf("\n");
	HeapDestroy(&hp);
}
int main()
{
	TestHeap();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21