题目：堆的构建
给定关键码集合，用筛选法构建小顶堆，并按照层序遍历方式输出构建的堆中所有节点。
输入样例：
19 8 35 65 40 3 7 45
输出样例：
3 8 7 45 40 35 19 65
解题思路👇
- 首先要定义堆MinHeap这个类，MinHeap类内成员有T模板指针heapArray用来存放堆数据，int 类型currentSize用来记录当前堆中的元素个数，int类型maxSize用来表示堆的大小。
- 其次要理清楚堆的结构
//数组下标范围
i<maxSize && i>=0
//根结点下标为0
root_index = 0
//层次遍历第i个结点的值等于数组第i-1个元素
value(i) = array[i-1]
//堆中第i个元素的左孩子下标i*2+1
left_child_index(i) = i*2+1
//堆中第i个元素的右孩子下标i*2+2
right_child_index(i) = i*2+2
//堆中第i个元素的父结点下标i/2-1
parent(i) = i/2-1
- 关键一步就是定义函数SiftDown()，核心原理就是向下寻找比目标元素小的孩子，进行变量交换，直到形成最小堆为止。
- 然后开始定义函数BuildHeap()用于堆的构造，具体操作是先把输入流内的数据依次存入堆内，然后利用函数SiftDown()来依次调整顺序，形成最小堆结构，最后将函数BuildHeap()加入到MinHeap类构造函数里以便于创建时调用。
代码示例👇
#include<iostream>
using namespace std;
template<class T>
class MinHeap {
private:
T* heapArray;//存放堆数据的数组
int currentSize;//当前堆中的元素个数
int maxSize;//堆的大小
//构建堆
void BuildHeap() {
cout << "你想加入多少元素？" << endl;
int size;
cin >> size;
currentSize = size;
cout << "请加入你的元素：" << endl;
for (int i = 0; i < size; i++) {
T value;
cin >> value;
heapArray[i] = value;
}
for (int i = currentSize / 2 - 1 ; i >= 0; i--) {
SiftDown(i);
}
}
public:
//构造函数，参数n为堆的大小
MinHeap(const int n) {
if (n <= 0) {
return;
}
currentSize = 0;
maxSize = n;
heapArray = new T[maxSize];
BuildHeap();
}
//虚析构函数
virtual ~MinHeap() {
delete[]heapArray;
}
//层序遍历打印堆中元素
void print() {
for (int i = 0; i < currentSize; i++) {
cout << heapArray[i] << " ";
}
}
//返回左孩子的位置
int LeftChild(int pos)const {
return 2 * pos + 1;
}
//返回右孩子的位置
int RightChild(int pos)const {
return 2 * pos + 2;
}
//返回父结点的位置
int Parent(int pos)const {
return (pos - 1) / 2;
}
//从pos开始向下筛选
void SiftDown(int pos) {
int i = pos;
int j = LeftChild(i);
T temp = heapArray[i];
while (j < currentSize) {
if ((j < currentSize - 1) && (heapArray[j] > heapArray[j + 1])) {
j++;
}
if (temp > heapArray[j]) {
heapArray[i] = heapArray[j];
i = j;
j = LeftChild(j);
}
else {
break;
}
}
heapArray[i] = temp;
}
};
int main() {
MinHeap<int> test(INT_MAX / 8);
test.print();
}运行效果👇
