- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我一直在研究 C++ 中的堆排序函数,它遵循我们类(class)书籍《算法导论》第 3 版中的逻辑,但没有得到所需的输出。一直在脑海中解决这个问题并且很接近,但我没有看到我的错误。我正在使用 vector 并省略了从单独的文本文件中读取值的代码。
关于我在每个版本中的索引哪里出了问题有什么想法吗?添加,我用来测试的输入列表是 10 15 8 3 16 20 11 12 5 7 4 1 19 13 2 6 9 14 17 18。
我尝试的第一种方法更接近本书,但给出的输出为 10 19 20 15 17 16 11 12 13 9 18 14 8 7 6 4 3 2 5 1。如果我能弄清楚我是如何弄乱索引的,这是我的首选解决方案。
void maxHeapify(vector<int>&);
void buildMaxHeap(vector<int>&);
void heapSort(vector<int>&);
int main(int argc, char * argv[])
{
if (argc <= 1)
{
std::cerr << "A file was not found or is not accessable." << std::endl;
return (1);
}
vector<int> list;
int loc;
ifstream fin(argv[1]);
while (fin >> loc)
{
list.push_back(loc);
}
// print unsorted list
cout << "Unsorted List:\n";
for (int i = 0; i < list.size(); ++i)
cout << list[i] << ' ';
cout << endl;
heapSort(list);
// print sorted list
cout << "Sorted List:\n";
for (int i = 0; i < list.size(); ++i) {
cout << list[i] << " ";
}
cout << endl;
cin.get();
return(0);
}
/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;
if ((l <= A.size()) && (A[l] > A[i]))
largest = l;
else
largest = i;
if ((r <= int(A.size())) && (A[r] > A[largest]))
largest = r;
if (largest != i)
{
swap(A[i], A[largest]);
maxHeapify(A, largest);
}
}
void buildMaxHeap(vector<int>& A)
{
for (int i = int((A.size()-1) / 2); i >= 1; i--)
{
maxHeapify(A, i);
}
}
void heapSort(vector<int>& A)
{
buildMaxHeap(A);
for (int i = int(A.size()-1); i >= 2; i--)
swap(A[1], A[i]);
maxHeapify(A, 1);
}
}
我尝试的第二种方法以输出 2 1 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 到 50 结束,这是一个随机排序的 50 个整数列表,但是在只有 20 个随机整数的列表中是正确的。代码如下:
void maxHeapify(vector<int>&, int, int);
void buildMaxHeap(vector<int>&, int);
void heapSort(vector<int>&, int);
int main(int argc, char * argv[])
{
if (argc <= 1)
{
std::cerr << "A file was not found or is not accessable." << std::endl;
return (1);
}
vector<int> list;
int loc;
ifstream fin(argv[1]);
while (fin >> loc)
{
list.push_back(loc);
}
// print unsorted list
cout << "Unsorted List:\n";
for (int i = 0; i < list.size(); ++i)
cout << list[i] << ' ';
cout << endl;
clock_t begin = clock();
heapSort(list, int(list.size() - 1));
clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; //only reports in seconds, need to replace.
printf("Heap Sort Elasped time is %0.6f seconds.", elapsed_secs);
cout << endl;
// print sorted list
cout << "Sorted List:\n";
for (int i = 0; i < list.size(); ++i) {
cout << list[i] << " ";
}
cout << endl;
cin.get();
return(0);
}
/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;
if ((l <= n) && (A[l - 1] > A[i - 1]))
largest = l;
else
largest = i;
if ((r <= n) && (A[r - 1] > A[largest - 1]))
largest = r;
if (largest != i)
{
swap(A[i - 1], A[largest - 1]);
maxHeapify(A, largest, n);
}
}
void buildMaxHeap(vector<int>& A, int n)
{
for (int i = n / 2; i >= 1; i--)
{
maxHeapify(A, i, n);
}
}
void heapSort(vector<int>& A, int n)
{
buildMaxHeap(A, n);
for (int i = n; i >= 2; i--)
{
swap(A[0], A[i]);
maxHeapify(A, 1, i - 1);
}
}
最佳答案
书中提供的算法将索引视为 1,2,3....N
, 它们从 1 开始。
所以只要遵循算法但记住一件事当我们访问数组时我们必须从索引中减去 1
所以你的第一个方法代码应该是:
void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;
if ((l <= n) && (A[l-1] > A[i-1]))
largest = l;
else
largest = i;
if ((r <= n) && (A[r-1] > A[largest-1]))
largest = r;
if (largest != i)
{
swap(A[i-1], A[largest-1]);
maxHeapify(A, largest, n);
}
}
在第二种方法中,您做错的是您正在检查关于基于 0 的索引 的边界。
我们不能通过此处基于 0 的索引,因为对于 0 索引,左 child 在索引 1 处,但 2*0 是0 ,所以 唯一的方法是在任何地方都使用基于 1 的索引,并且仅在访问您减去的元素时使用 - 1
关于c++ - 堆排序从介绍到使用 vector 的 C++ 实现中的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40168231/
晚上在 QQ 上看到昵称为“乱码”的好友回答了搜搜问问里一个问题: 在VBS中有办法定义字节数组么? 在VBS中有办法定义字节数组么?就是字节子类型数组(VarType是8209的那种)注意不是V
例如,员工管理应用程序可能包括一个EmPloyee 类。然后可以用这个类来创建和维护特定实例,比如Gonn和Sally。 根据预定义的类创建对象常称为类的实例化(class insta
在自然语言中,我们理解抽象的概念是,一个物体的一种大的描述,这种描述对某类物体来说是共有的特性。那么在PHP中也是一样的,我们把一个类进行抽象,可以指明类的一般行为,这个类应该是一个模板,它指示它的
DBA_2PC_PENDING Oracle会自动处理分布事务,保证分布事务的一致性,所有站点全部提交或全部回滚。一般情况下,处理过程在很短的时间内完成,根本无法察觉到。但是,如果在commit或
目录 计算过程 投影分量计算 假设你有一家理发店,已经记录了过去一年中所有顾客的头发长度和发型偏好的数据。现在你想从这些数据中提取一些主要的信息,比如顾客最常
Object.defineProperty函数会直接在一个对象上定义一个新的属性,或者修改一个对象的现有属性,并返回此对象。 一、简单使用 const obj = {} Object.defineP
SPL官网 http://www.scudata.com.cn/ 介绍 业务逻辑经常包含较复杂的流程和计算,同时涉及数据库的读写。由于授权麻烦、影响数据库安全、无法迁移、技术要求高、编写困难等原因,很
SPL官网 http://www.scudata.com.cn/ 介绍 业务逻辑经常包含较复杂的流程和计算,同时涉及数据库的读写。由于授权麻烦、影响数据库安全、无法迁移、技术要求高、编写困难等原因,很
一 点睛 Thrift 是一歀基于 CS 架构的 RPC 框架,最初由 Facebook 研发,2008 年转入 Apache 组织。开发人员可以使用 Thrift 提供的 IDL(接口定义语言)来定
数据库应用程序与主应用程序分开存在,并存储数据集合。 每个数据库都使用一个或多个API来创建,访问,管理,搜索和复制其包含的数据。 数据库还使用非关系数据源,例如对象或文件。 然而,数据库证明是大数
介绍 Ant是一个 Apache 基金会下的跨平台的基于 Java 语言开发的构件工具。在我们详细了解 Apache Ant 之前, 让我们来讲解为什么构建工具是需要最先了解的。 构建工具的需求
我现在正在尝试学习ocaml,并希望从一个小程序开始,生成所有位组合: [“0”,“0”,“0”] [“0”,“0”,“1”] [“0”,“1”,“0”] ... 等等 我的想法是下面的代码: let
我正在做我的介绍 C 类(class)作业,我的任务是执行以下任务...... 为一个函数编写代码,该函数通过值接收两个参数(a 和 b)并通过引用具有另外两个参数(c 和 d)。所有参数都是双倍的。
我希望提供有关我网站内容的快速演示,以及如何在用户访问我的页面后立即以正确的方式使用它们。我希望使用顶部的弹出式窗口进行演示。 我的意思是小信息框,一个接一个地通知用户各个步骤。任何人都可以帮助我如何
与C、Java等语言一样,JavaScript中可以用&&、||、!三个逻辑判断符来对boolean值进行逻辑判断。与C、Java不同的是,JavaScript中逻辑与(&&
JavaScript中,==与===操作符均可用于判断两个值是否相等;不同之处在于,如果进行判断的两个值类型不一致,===操作符会直接返回false,而==操作符则会在类型转换后再进行判断。详细的判
JavaScript中,object转换为boolean的操作非常简单:所有的object转换成boolean后均为true;即使是new Boolean(false)这样的object在转换为bo
在android开发中,当不满足触发条件就按返回键的时候,就要对此进行检测。尤其是当前Activity需要往前一个Activity传送消息时。即Activity1跳转到Activity3如果采用的是
背景 当要求系统启动一个应用程序时,系统会先查找当前命令是否是内部命令,若不是,则在当前目录下查找,如果仍没有找到,则在系统变量 Path 指定的路径去查找。JDK(Java Developmen
概述 想做一个微信的公众平台,阅读了微信官方给的网址接入的示例代码,发现有个问题好像一直都是半知半解的,就是在类里边直接使用$_GET。仔细查了下关于这方面的知识,发现PHP中这部分的基础知识掌握
我是一名优秀的程序员,十分优秀!