建小顶堆以及堆的顺序输出

建小顶堆以及堆的顺序输出

顺序输出函数是 deletenode();
原理： 输出堆顶元素，然后再进行堆调整，重复直到全部输出
细节： 通过交换堆顶元素跟堆尾元素然后让堆-1，可以不用避免移动数组

//采用数组形式的完全二叉树进行建堆
#include<stdio.h>
/// <summary>
/// h数组用来存放堆元素
/// n是堆中元素个数
/// </summary>
int h[100];
int n;



/// <summary>
/// 交换h[i]与h[j]
/// </summary>
/// <param name="t"></param>
/// <param name="i"></param>
void swap(int t, int i)//exchange h[t] and h[i]
{
	int temp;
	temp = h[t];
	h[t] = h[i];
	h[i] = temp;
	return;
}


/// <summary>
/// 向下调整，建立小顶堆
/// </summary>
/// <param name="i"></param>
void siftdown(int i) 
{
	int t, flag = 0;
	/// <summary>
	/// 首先查看当前i是否有左右孩子，有左孩子则与左孩子比较，若是比左孩子大，则更新t的值标记左孩子，否则t标记当前结点，
	/// 然后查看是否有又孩子，若是有右孩子，被标记结点与右孩子比较，然后更新标记结点，进行更新，
	/// 更新完成则让flag值置1，表示更新完成退出向下调整函数
	/// </summary>
	/// <param name="i"></param>
	while (i * 2 <= n && flag == 0)
	{
		if (h[i] > h[i * 2])
		{
			t = i * 2;
		}
		else
		{
			t = i;
		}
		if (i * 2 + 1 <= n)
		{
			if (h[t] > h[i * 2 + 1])
			{
				t = i * 2 + 1;
			}
		}
		if (t != i)//smaller nodes found
		{
			swap(t, i);//exchange node
			i = t;//update i
		}
		else
		{
			flag = 1;//no adjustment required
		}
	}
	return;
}


/// <summary>
/// 按顺序输出堆元素
/// </summary>
/// <returns></returns>
int deletenode()
{
	int temp;
	temp = h[1];
	h[1] = h[n];
	n--;
	siftdown(1);//adjust top elements
	return temp;
}

/// <summary>
/// 完全二叉树最后一个非叶结点是第n/2个结点（向下取整）因为有孩子是2*n+1
/// </summary>
void creat() {
	for (int i = n / 2; i >= 1; i--)
	{
		siftdown(i);
	}
	return;
}



int main()
{
	int  num;//enter the number
	scanf("%d", &num);
	for (int i = 1; i <= num; i++)
	{
		scanf("%d", &h[i]);//please enter from 1
	}
	n = num;
	//Reactor building
	creat();
	printf("堆初始化后的序列：\n");
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", h[i]);
	}

	//此处用 num 因为 n的值在deletenode函数中会变化
	printf("\n排序后:\n");
	for (int i = 1; i <= num; i++)
	{
		printf("%d ", deletenode());
	}
	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
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