Login
Register
Problem list
Online status
RockyChen0205
:
2023-12-19 17:14:59
构建最小堆 #include
#include
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
& data) { int tmp = data[i]; data[i] = data[j]; data[j] = tmp; } void heapify(int i,vector
& 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
> result; for(int i=0;i
temp; int n; cin>>n; for(int j=0;j
>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
sptnk1
:
2023-12-11 23:41:35
#include
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
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
221128
:
2021-10-28 00:09:46
221128
:
2021-10-28 00:05:08
flag{eW91X2FyZV9hcnJlc3RlZA==}
qwwwwq
:
2021-10-27 23:19:41
flag{eW91X2FyZV9pbmplY3RlZA==}
Post Your Comment