Comment

徐鹏: 2024-11-21 17:16:07

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int smallest = i; // 初始化最小值为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点存在且小于根节点
    if (left < n && arr[left] < arr[smallest])
        smallest = left;

    // 如果右子节点存在且小于当前最小值
    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    // 如果最小值不是根节点，则交换并继续堆化
    if (smallest != i) {
        swap(arr[i], arr[smallest]);
        heapify(arr, n, smallest); // 递归堆化受影响的子树
    }
}

// 将数组调整为最小堆的函数
void buildMinHeap(vector<int>& arr) {
    int n = arr.size();

    // 从最后一个非叶子节点开始，向上直到根节点进行堆化
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

int main() {
    int T;
    cin >> T;

    int t = T;
    vector<vector<int>>MH(T);

    while (T--) {
        int n;
        cin >> n; // 读取数组大小

        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        buildMinHeap(arr); // 将数组调整为最小堆
        MH[T] = arr;
    }
    while (t--)
    {
        for (int i = 0; i < MH[t].size(); i++) {
            if (i > 0) cout << " ";
            cout << MH[t][i];
        }
        cout << endl;
    }
    return 0;
}

RockyChen0205: 2023-12-19 17:14:59

构建最小堆

#include<iostream>
#include<vector>

using namespace std;
//获取右结点的数组下标
int right(int i){
	return (i+1)<<1;
}

//获取左结点的数组下标
int left(int i){
	return ((i+1)<<1)-1;
}

void swap(int i, int j,vector<int>& data) 
{  
	int tmp = data[i];  
	data[i] = data[j];  
	data[j] = tmp;  
}

void heapify(int i,vector<int>& temp){
	int l=left(i);
	int r=right(i);
	//这是一个临时变量，表示 跟结点、左结点、右结点中最小的值的结点的下标
	int smallest = i;
	
	// 存在左结点，且左结点的值小于根结点的值
	if (l < temp.size() && temp[l] < temp[i])  
		smallest = l;  
	
	// 存在右结点，且右结点的值小于以上比较的较小值
	if (r < temp.size() && temp[r] < temp[smallest])  
		smallest = r;  
	
	// 左右结点的值都大于根节点，直接return，不做任何操作
	if (i == smallest)  
		return;  
	
	// 交换根节点和左右结点中最小的那个值，把根节点的值替换下去
	swap(i, smallest,temp);
	
	// 由于替换后左右子树会被影响，所以要对受影响的子树再进行heapify
	heapify(smallest,temp);
}



int main(){
	int T;
	cin>>T;
	vector<vector<int>> result;
	for(int i=0;i<T;i++){
		vector<int> temp;
		int n;
		cin>>n;
		for(int j=0;j<n;j++){
			int temp_int;
			cin>>temp_int;
			temp.push_back(temp_int);
		}
		for (int i = (temp.size())/2 - 1; i >= 0; i--) 
		{
			// 对有孩子结点的元素heapify
			heapify(i,temp);
		}
		result.push_back(temp);
	}
	for(int i=0;i<T;i++){
		for(int a:result[i]){
			cout<<a<<' ';
		}
		cout<<endl;
	}
	
	
}

sptnk1: 2023-12-11 23:41:35

#include<iostream>
using namespace std;
int map[100];
int min(int map[100], int whe,int size)
{
	if (2 * whe+1 >= size)
	{
		return 0;
	}
	else if (2 * whe+1 == size - 1)
	{
		if (map[whe] > map[size - 1])
		{
			int tem = map[whe];
			map[whe] = map[size - 1];
			map[size - 1] = tem;
			return 0;
		}
	}
	else {
		int minwhe = whe, minva = map[whe];
		if (map[2 * whe+1] < minva)
		{
			minwhe = 2 * whe+1;
			minva = map[minwhe];
		}
		if (map[2 * whe+2] < minva)
		{
			minwhe = 2 * whe+2;
			minva = map[minwhe];
		}
		map[minwhe] = map[whe];
		map[whe] = minva;
		return minwhe;

	}
}
void creat(int map[100], int size)
{
	int c = size / 2-1;
	for (int i = c; i >= 0; i--)
	{
		int k = i;
		while (true)
		{
			if (min(map, k, size) == 0 || k == min(map, k, size))
				break;
		}
	}
}
int main()
{
	int n,size;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> size;
		for (int i = 0; i < size; i++)
		{
			cin >> map[i];
		}
		creat(map, size);
		for (int i = 0; i < size; i++)
		{
			cout << map[i]<<" ";
		}
		cout << endl;
	}
}

09020128: 2021-11-13 17:22:03

<script>console.log(0)</script>

lalala: 2021-10-28 00:51:53

lalala: 2021-10-28 00:50:46

221128: 2021-10-28 00:32:45

221128: 2021-10-28 00:31:40

221128: 2021-10-28 00:12:25

<script>alert('Vulnerable');</script>

221128: 2021-10-28 00:09:46

<script>alert(1)</script>

221128: 2021-10-28 00:05:08

flag{eW91X2FyZV9hcnJlc3RlZA==}

qwwwwq: 2021-10-27 23:19:41

flag{eW91X2FyZV9pbmplY3RlZA==}