混淆了堆的两种不同实现
Confused with Two different implementation of Heap
函数 1
void min_heapify(int arr[],int n, int i){
int j, temp;
temp = arr[i];
j = 2 * i;
while (j <= n)
{
if (j < n && arr[j+1] < arr[j])
j = j + 1;
if (temp < arr[j])
break;
else if (temp >= arr[j])
{
arr[j/2] = arr[j];
j = 2 * j;
}
}
arr[j/2] = temp;
}
函数 2
void max_heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] < arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] < arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
问题详情
这里堆化的工作方式与 min_heap 相同,但问题是,我在下面的问题中使用了堆来解决它,但不幸的是,我通过观看麻省理工学院讲座实现的函数 2 不起作用对于这个问题,在网上看了一段时间后,我发现第一个函数可以无缝地解决这个问题。我只是很困惑,它们不是相同的功能吗? ------
问题
是的!!问题名称反映了您的任务;只需添加一组数字。但是您可能会觉得自己居高临下,写一个 C/C++ 程序只是为了添加一组数字。这样的问题只会质疑你的博学。所以,让我们为它添加一些别出心裁的味道。
加法运算现在需要成本,成本是这两个相加的总和。所以,1和10相加,需要11的成本,如果要1、2、3相加,有几种方法-
1 + 2 = 3, cost = 3
1 + 3 = 4, cost = 4
2 + 3 = 5, cost = 5
3 + 3 = 6, cost = 6
2 + 4 = 6, cost = 6
1 + 5 = 6, cost = 6
Total = 9
Total = 10
Total = 11
我希望你已经理解了你的任务,添加一组整数以使成本最小。
输入
每个测试用例将以一个正数开始,N (2 ≤ N ≤ 5000) 后跟 N 个正整数(均小于 100000)。输入在 N 的值为零的情况下终止。这种情况不应该处理。
输出
对于每种情况,在一行中打印最小的加法总成本。
样本输入
3
1 2 3
4
1 2 3 4
0
样本输出
9
19
function2 中的 swap
函数有问题。
C是按值调用,所以
swap(arr[i], arr[largest]);
无法交换数组中的值。
交换函数需要交换值的地址:
swap(int *v1, int *v2) {
int tmp = *v1;
*v1 = *v2;
*v2 = tmp;
}
电话会是:
swap(&arr[i], &arr[largest]);
好的,我找到了解决方案,条件检查中存在错误,在 if 条件中我们检查 if (left <= n) this was previously (left < n) 这就是为什么它不起作用的原因那个问题。好的谢谢
void min_heapify(int arr[],int n, int i){
int lowest = i; // Initialize lowest as root
int left = 2*i ;
int right = 2*i + 1;
// If child is lower than root
if(left <= n && arr[left] < arr[lowest]){
lowest = left;
}
// If right child is lower than lowest
if(right <= n && arr[right] < arr[lowest]){
lowest = right;
}
// If lowest is not root
if(lowest != i){ // also break condition
swap(arr[i], arr[lowest]);
//Recursively heapify
min_heapify(arr, n, lowest);
}
函数 1
void min_heapify(int arr[],int n, int i){
int j, temp;
temp = arr[i];
j = 2 * i;
while (j <= n)
{
if (j < n && arr[j+1] < arr[j])
j = j + 1;
if (temp < arr[j])
break;
else if (temp >= arr[j])
{
arr[j/2] = arr[j];
j = 2 * j;
}
}
arr[j/2] = temp;
}
函数 2
void max_heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] < arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] < arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
问题详情
这里堆化的工作方式与 min_heap 相同,但问题是,我在下面的问题中使用了堆来解决它,但不幸的是,我通过观看麻省理工学院讲座实现的函数 2 不起作用对于这个问题,在网上看了一段时间后,我发现第一个函数可以无缝地解决这个问题。我只是很困惑,它们不是相同的功能吗? ------
问题
是的!!问题名称反映了您的任务;只需添加一组数字。但是您可能会觉得自己居高临下,写一个 C/C++ 程序只是为了添加一组数字。这样的问题只会质疑你的博学。所以,让我们为它添加一些别出心裁的味道。
加法运算现在需要成本,成本是这两个相加的总和。所以,1和10相加,需要11的成本,如果要1、2、3相加,有几种方法-
1 + 2 = 3, cost = 3
1 + 3 = 4, cost = 4
2 + 3 = 5, cost = 5
3 + 3 = 6, cost = 6
2 + 4 = 6, cost = 6
1 + 5 = 6, cost = 6
Total = 9
Total = 10
Total = 11
我希望你已经理解了你的任务,添加一组整数以使成本最小。
输入
每个测试用例将以一个正数开始,N (2 ≤ N ≤ 5000) 后跟 N 个正整数(均小于 100000)。输入在 N 的值为零的情况下终止。这种情况不应该处理。
输出
对于每种情况,在一行中打印最小的加法总成本。
样本输入
3
1 2 3
4
1 2 3 4
0
样本输出
9
19
function2 中的 swap
函数有问题。
C是按值调用,所以
swap(arr[i], arr[largest]);
无法交换数组中的值。
交换函数需要交换值的地址:
swap(int *v1, int *v2) {
int tmp = *v1;
*v1 = *v2;
*v2 = tmp;
}
电话会是:
swap(&arr[i], &arr[largest]);
好的,我找到了解决方案,条件检查中存在错误,在 if 条件中我们检查 if (left <= n) this was previously (left < n) 这就是为什么它不起作用的原因那个问题。好的谢谢
void min_heapify(int arr[],int n, int i){
int lowest = i; // Initialize lowest as root
int left = 2*i ;
int right = 2*i + 1;
// If child is lower than root
if(left <= n && arr[left] < arr[lowest]){
lowest = left;
}
// If right child is lower than lowest
if(right <= n && arr[right] < arr[lowest]){
lowest = right;
}
// If lowest is not root
if(lowest != i){ // also break condition
swap(arr[i], arr[lowest]);
//Recursively heapify
min_heapify(arr, n, lowest);
}