数据结构堆及利用堆实现排序_堆排序实现某个元素查找打印输出

堆也一种树形结构，其父节点值比左右子节点值都大，而子节点又比其子节点的子节点值要大，依次类推，最大值出现在根节点，最小值出现在叶节点，但是堆中的左右子节点值并没有顺序，因此利用算法可以实现堆排序。
排序思想是依次交换根节点和末尾节点的元素，然后利用下沉算法实现当前根节点的元素处于正确的位置，之后重复进行交换和下沉，其中与跟结点交换的元素每次都要比堆元素个数小1，而且每次交换完后下沉根节点时，与根节点交换过的元素不参与下沉。（具体代码见堆排序函数）

#incude<iostream>
using namespace std;
/* 数组实现堆 */
template<class T>
class heap
{
private:
	T* element;
	int capacity;
	int size;
public:
	
	heap(int theCapacity)
	{
		capacity = theCapacity;
		element = new T[capacity + 1];
		size = 0;
	}
	~heap()
	{
		delete[] element;
	}
	/* 判断堆是否为空 */
	bool empty()
	{
		if (size == 0)
			return true;
		else
			return false;
	}
	/* 改变数组容量 */
	void resize()
	{
		element = new T[(capacity << 1) + 1];
	}
	/* 获取元素个数 */
	int getsize()
	{
		return this->size;
	}
	/* 交换索引i和索引j处的值 */
	void swap(int i, int j)
	{
		T temp = element[i];
		element[i] = element[j];
		element[j] = temp;
	}
	/* 判断索引i出的值是否小于索引j处的值 */
	bool minIndexValue(int i, int j)
	{
		if (element[i] < element[j])
			return true;
		else
			return false;
	}
	/* 向堆中插入元素 */
	void insert(T theValue)
	{
		element[++size] = theValue;
		shiftUp(size);
	}
	/* 上浮指定索引处的元素，使其处于正确位置 */
	void shiftUp(int k)
	{
		while (k > 1)
		{
			if (element[k] > element[int(k / 2)])
				swap(k, k / 2);
			k = int(k / 2);
		}
	}
	/* 删除堆中指定索引的元素 */
	T Delete(int theIndex)
	{
		T delValue = element[theIndex];
		swap(theIndex, size);
		element[size] = "\0";
		size--;
		shiftDown(theIndex);
		return delValue;
	}
	/* 下沉指定索引处的元素，使其处于正确位置 */
	void shiftDown(int k)
	{
		while (2 * k <= size)
		{
			int max;
			if (2 * k + 1 <= size)
			{
				if (element[2 * k] < element[2 * k + 1])
				{
					max = 2 * k + 1;
				}
				else
				{
					max = 2 * k;
				}
			}
			else
			{
				max = 2 * k;
			}
			if (element[k] < element[max])
			{
				swap(k, max);
				k = max;
			}
			else
			{
				break;
			}
		}
	}
	/* 重载的下沉函数 */
	void shiftDown(int k,int theSize)
	{
		while (2 * k <= theSize)
		{
			int max;
			if (2 * k + 1 <= theSize)
			{
				if (element[2 * k] < element[2 * k + 1])
				{
					max = 2 * k + 1;
				}
				else
				{
					max = 2 * k;
				}
			}
			else
			{
				max = 2 * k;
			}
			if (element[k] < element[max])
			{
				swap(k, max);
				k = max;
			}
			else
			{
				break;
			}
		}
	}
	/* 利用堆进行排序 */
	void heapSort(T* theElement,int theSize)
	{
		//将原数组元素拷贝到堆中
		if(theSize > capacity)
			resize();
		for (int i = 0; i < theSize; i++)
		{
			element[++size] = theElement[i];
			
		}
		//然后从数组长度的一半处开始循环调用下沉函数，是每一个元素都处于正确的堆位置
		for (int i = size / 2; i > 0; i--)
		{
			shiftDown(i);
		}
		cout << "排序前顺序为：" << endl;
		output();
		//之后开始排序，使堆中元素从上至下从左到右依次增大
		//排序思想是将第一个元素与最后一个元素交换，然后调用重载的下沉函数使交换后的第一个元素处于正确位置（此处交换后最后的一个元素不参与）
		//然后重复上述步骤，让第一个元素与倒数第二个交换，然后下沉第一个元素（倒数第二个也不参与），依此类推。

		//定义一个变量存储未排序的对元素最大索引,便于做下沉
		int maxIndex = theSize;
		for (; maxIndex > 1; maxIndex--)
		{
			swap(1, maxIndex);
			shiftDown(1,maxIndex - 1);
		}
	}
	/* 前序遍历输出堆元素 */
	void preOrder(int theIndex)
	{
		if (theIndex <= size )
		{
			cout << element[theIndex] << ",";
			int theIndex1 = (2 * theIndex);
			int theIndex2 = (2 * theIndex) + 1;
			preOrder(theIndex1);
			preOrder(theIndex2);
		}
	}
	/* 中序遍历输出堆元素 */
	void inOrder(int theIndex)
	{
		if (theIndex <= size)
		{
			int theIndex1 = (2 * theIndex);
			int theIndex2 = (2 * theIndex) + 1;
			inOrder(theIndex1);
			cout << element[theIndex] << ",";
			inOrder(theIndex2);
		}
	}
	/* 直接按顺序输出element数组元素 */
	void output()
	{
		for (int i = 1; i <= size; i++)
		{
			cout << element[i] << ",";
		}
		cout << endl;
	}
};
/*测试代码*/
int main() 
{
	heap<string>a(10);

	string num[] = { "A","B","C","D","E","F","G","H","I" ,"J","K"};
	a.heapSort(num,11);
	cout << "排序后顺序为:" << endl;
	a.output();
	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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220

此处可以先采用前序遍历和中序遍历（代码已给出，只需在main函数调用）将树形结构画出来，便于观察其中的排序过程。