顺序堆_顺序堆齐

SeqHeap.h

#pragma once

#include<iostream>
#define MAXSIZE 1000000
using namespace std;

template <class DataType>
class SeqHeap
{
public:
	SeqHeap();                                         //无参构造函数构建无序堆
	SeqHeap(DataType arr[], int n);                    //有参构造函数构建无序堆
	~SeqHeap();                                        //析构函数
	void MakeMaxSeqHeap(SeqHeap *h);                   //构建最大顶堆
	void MakeMinSeqHeap(SeqHeap *h);                   //构建最小顶堆
	void PrintSeqHeap(SeqHeap h);                      //打印堆
	void MaxHeapSort(SeqHeap *h);                      //堆排序:从小到大（小根堆）
	void MinHeapSort(SeqHeap *h);                      //堆排序:从大到小（大根堆）
	void Sink(DataType arr[], int k, int N);           //由上到下的堆有序化（下沉）:根结点元素值比其子结点小的就下沉（得到的堆是大根堆）
	void Swin(DataType arr[], int k, int N);           //由下到上的堆有序化（上浮）:子结点元素值比其根结点大的就上浮（得到的堆是大根堆）
	void SinkConversely(DataType arr[], int k, int N); //由上到下的堆有序化（下沉）:根结点元素值比其子结点大的就下沉（得到的堆是小根堆）
	void SwinConversely(DataType arr[], int k, int N); //由下到上的堆有序化（上浮）:根结点元素值比其子结点大的就下沉（得到的堆是小根堆）
	void Swap(DataType arr[], int i, int j);           //交换下标为 i、j 两个元素
	void OutputInFile(SeqHeap h, string filename);     //把排序结果输出到文件中。
	void Clear(SeqHeap *h);
	bool Less(DataType v, DataType w);                 //若 v < w，返回true; 否则返回 false

private:
	DataType *heap = new DataType[MAXSIZE + 1]; //存储堆元素：heap[0]不存储数据
	int size; //堆的元素个数
};


/*

基本概念：

1、完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。
2、满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。

堆定义：
1、堆是一颗完全二叉树；
2、堆中的某个结点的值总是大于等于（最大堆）或小于等于（最小堆）其孩子结点的值。
3、堆中每个结点的子树都是堆树。

*/
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

SeqHeap.cpp

#include"SeqHeap.h"

template<class DataType>
SeqHeap<DataType>::SeqHeap()
{
	size = 0;
}

template<class DataType>
SeqHeap<DataType>::SeqHeap(DataType arr[], int n)
{
	for (int i = 0; i < n; i++) {
		heap[i+1]=arr[i];
	}
	size = n;
}

template<class DataType>
SeqHeap<DataType>::~SeqHeap()
{
}

template<class DataType>
void SeqHeap<DataType>::MakeMaxSeqHeap(SeqHeap *h)
{
	h->MaxHeapSort(h);//构建最大顶堆
}

template<class DataType>
void SeqHeap<DataType>::MakeMinSeqHeap(SeqHeap *h)
{
	h->MinHeapSort(h);//构建最小顶堆
}

template<class DataType>
void SeqHeap<DataType>::PrintSeqHeap(SeqHeap h)
{
	for (int i = 1; i <= size; i++) {
		cout << h.heap[i] << " ";
		if (i%20 == 0)
			cout << endl;
	}
	cout << endl;
}

template<class DataType>
void SeqHeap<DataType>::MaxHeapSort(SeqHeap * h)
{
	int N = h->size;
	for (int k = N / 2; k >= 1; k--) {
		SinkConversely(h->heap, k, N);//此步是堆的构造：构造的结果是部分堆有序，即头结点的值是最小的。
	}
	while (N > 1)
	{
		Swap(h->heap, 1, N--);
		SinkConversely(h->heap, 1, N);
	}
}

template<class DataType>
void SeqHeap<DataType>::MinHeapSort(SeqHeap *h)
{
	int N = h->size;
	for (int k = N / 2; k >= 1; k--) {
		Sink(h->heap, k, N);//此步是堆的构造：构造的结果是部分堆有序，即头结点的值是最大的。
	}
	while (N > 1)
	{
		Swap(h->heap, 1, N--);
		Sink(h->heap, 1, N);
	}
}

/*
  arr[]：即 h->heap
      k：把位置为k的结点下沉
        【该结点的特点：heap[k] < heap[2*k] (OR||AND) heap[k]<heap[2*k+1]，即该结点值比其两个子结点中的一个或两个小 】
      N：堆里（即heap[]）有N个元素，即 h->size的值
*/
template<class DataType>
void SeqHeap<DataType>::Sink(DataType arr[], int k, int N)
{
	while (2*k <= N) //当结点k 的子结点2*k 不超过当前数组元素的最大下标时【结点 2*k 是 结点 k 的子结点】，才有机会继续下沉
	{
		int j = 2 * k;
		if (j < N && Less(arr[j], arr[j + 1]))
			j++;
		if (Less(arr[j], arr[k])) break;//also could be !Less(arr[k], arr[j]),即当 arr[k]>arr[j]时跳出循环体
		Swap(arr, k, j);
		k = j;
	}
}

/*
  arr[]：即 h->heap
      k：把位置为k的结点上浮【该结点的特点：heap[k] > heap[k/2]，即该结点值比其父结点值大 】
      N：堆里（即heap[]）有N个元素，即 h->size的值
*/
template<class DataType>
void SeqHeap<DataType>::Swin(DataType arr[], int k, int N)
{
	while ( k>1 && Less(arr[k/2],arr[k]) )//若结点 k 不是根结点、且其值比其父结点大时，循环体进行，结点k上浮
	{
		Swap(arr, k / 2, k);
		k = k / 2;
	}
}

template<class DataType>
void SeqHeap<DataType>::SinkConversely(DataType arr[], int k, int N)
{
	while (2 * k <= N) //当结点k 的子结点2*k 不超过当前数组元素的最大下标时【结点 2*k 是 结点 k 的子结点】，才有机会继续下沉
	{
		int j = 2 * k;
		if (j < N && Less(arr[j + 1], arr[j]))
			j++;
		if (Less(arr[k], arr[j])) break;//also could be !Less(arr[k], arr[j]),即当 arr[k]<arr[j]时跳出循环体
		Swap(arr, k, j);
		k = j;
	}
}

template<class DataType>
void SeqHeap<DataType>::SwinConversely(DataType arr[], int k, int N)
{
	while (k>1 && Less(arr[k / 2], arr[k]))//若结点 k 不是根结点、且其值比其父结点小时，循环体进行，结点k上浮
	{
		Swap(arr, k / 2, k);
		k = k / 2;
	}
}

template<class DataType>
void SeqHeap<DataType>::Swap(DataType arr[], int i, int j)
{
	DataType temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

template<class DataType>
void SeqHeap<DataType>::OutputInFile(SeqHeap h, string filename)
{
	ofstream outfile(filename);
	for (int i = 1; i <= size; i++) {
		outfile << h.heap[i] << endl;
	}
	outfile.close();
}

template<class DataType>
void SeqHeap<DataType>::Clear(SeqHeap * h)
{
	h->size = 0;
}

template<class DataType>
bool SeqHeap<DataType>::Less(DataType v, DataType w)
{
	return v < w;;
}

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