当我知道PQ在时间复杂度方面会更好的时候，我什么时候会选择Collections.sort()而不是PriorityQueue呢？
浏览 3提问于2014-03-23得票数 6
回答已采纳
6回答
为什么堆不稳定？
、、
我想弄明白为什么堆不稳定。我搜索过这个，但没有找到一个好的，直观的解释。
我理解稳定排序的重要性--它允许我们根据多个键进行排序，这是非常有益的(例如，进行多个排序，每个排序基于不同的键。因为每种类型都将保持元素的相对顺序，以前的排序可以加起来给出按多个标准排序的元素的最终列表)。然而，为什么堆不保存它呢？
谢谢你的帮忙!
浏览 16提问于2013-10-12得票数 39
回答已采纳
1回答
可以说，当大小为n的数组A中的所有元素都相同时，堆排序的运行时间是O(n)吗？
-->如果是这种情况，堆排序的运行时间是O(n)个最佳情况吗
浏览 1提问于2011-11-17得票数 5
回答已采纳
3回答
堆排序的应用
、、、
Heapsort是一种时间复杂度为O(nlogn)的排序算法，它使用O(1)空间复杂度进行排序。然而，我知道，因为它是不稳定的，它找不到多少应用程序(f.e。(与其他排序算法相比)。
我知道它是用来安排时间的。
堆排序的一些实际应用是什么？
编辑:正如@AProgrammer所指出的，快速排序也不稳定。
浏览 0提问于2013-04-08得票数 4
1回答
从快速排序开始，当递归深度超过基于要排序的元素数量的级别时，切换到堆排序。那是什么号码？是否有一个特定的范围或限制值？
浏览 2提问于2012-06-24得票数 7
回答已采纳
1回答
我们有一个包含1000000个元素的数组，我们需要找到100倍的值。有两个选项:首先用堆排序排序，然后通过二进制搜索搜索，第二顺序搜索。
如果没有计算，我会说第一种选择更好，但是..。在第二个选项中，在最坏的情况下，我们有num_of_elem * num_of_search = 100 * 1000000，在第一个选项中，(堆排序是O(nlogn))所以是(1000000*log(1000000))*100*log(1000000) = 1000000*20*100*20。这意味着第二种选择要好400倍。
我说对了吗？
浏览 0提问于2019-07-08得票数 0
回答已采纳
2回答
在哪种情况下可以使用堆排序？如我们所知，堆排序具有n×lg(n).的复杂性。但是它的使用要比快速合并排序少得多。那么，我们什么时候才能准确地使用这种堆类型?它的缺点是什么？
浏览 2提问于2013-08-10得票数 0
5回答
堆排序排序算法的最坏情况复杂度似乎为O(nlogn)，排序操作使用O(1)空间。
这似乎比大多数排序算法都要好。那么，为什么不总是使用堆排序作为排序算法(以及为什么人们使用像合并排序或快速排序这样的排序机制)？
此外，我还看到人们将“不稳定性”这一术语与堆排序一起使用。这意味着什么？
浏览 49提问于2011-11-29得票数 71
回答已采纳
2回答
内存容量小的排序
、、、、
使用2G的RAM对1G大小的字典(每个单词255个字符)进行排序的最佳方法是什么？我已经尝试过快速排序，但没有得到可以接受的结果。这是快速排序代码：
#include <iostream>
#include <fstream>
#include <cstring>
#define MAXL 4000000
using namespace std;
void swap(char *&ch1,char *&ch2)
{
char *temp = ch1;
ch1 = ch2;
ch2 = temp;
}
int par
浏览 3提问于2018-11-22得票数 0
我正在尝试实现Cormen中提供的堆排序算法。我的代码如下：
#include<stdio.h>
#include<conio.h>
void max_heapify(int *,int);
void build_max_heap(int *,int);
void heapsort(int *,int);
void swap(int,int);
int heapsize;
int main()
{
int *arr,n,i;
printf("E
浏览 3提问于2013-08-12得票数 2
回答已采纳
1回答
我正在尝试学习自排序，并发现资源是稀缺的。
我的问题是，在切换到堆排序之前，深度是如何计算的？有floor(log(length_of_data))x2，但我见过使用其他东西。原因是什么？我说的对吗?算法希望坚持使用快速排序，直到由于内存原因而需要切换到堆排序？
浏览 1提问于2016-10-11得票数 0
4回答
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
{
if(a[i] > a[j])
{
/* Swap a[i] and a[j] */
}
}
}
P.S.给出了一个算法的名称，可以很容易地找到相关的源代码。但我发现很难做到反之亦然:D
编辑哦！如果这是气泡排序，那么它的名称是什么：
for(int i=0; i<n; i++)
{
for(int j=0; j<n-1; j++)
{
浏览 2提问于2011-03-18得票数 6
回答已采纳
1回答
堆排序空间复杂度
、、、
我正在阅读Skiena的“算法设计手册”，特别是关于堆排序的部分。他说
它是就地排序，这意味着它不对包含要排序的元素的数组使用额外的内存。
书中的算法如下所示：
heapsort(item_type s[], int n)
{
int i;
priority_queue q;
make_heap(&q, s, n);
for (i=0; i<n; i++)
s[i] = extract_min(&q);
}
在我看来，除了条目的输入数组s之外，我们还在priority_queue变量中创建堆数据结构。这不意味着所需的空间复杂度是O(
浏览 3提问于2014-11-22得票数 1
3回答
堆排序不被视为稳定排序算法的原因
、、、、
在Java排序中，根据对随机数数组进行排序似乎是最好的排序算法，但我仍然看到堆排序不稳定，为什么呢？在对数组或随机数排序时，哪种排序算法应该被认为是最佳算法？
浏览 5提问于2015-08-04得票数 1
回答已采纳
3回答
在研究排序算法时，将其称为堆排序用于外部排序。当我们处理外部存储时，我不能弄清楚它在排序技术方面有什么不同？或者，堆排序唯一能被认为对外部排序有用的东西是什么？
有没有人能解释一下？
浏览 6提问于2018-01-06得票数 1
2回答
我正在复习。我想知道为什么它是在二叉树中实现的？它还能用别的树吗？比如三子节点树？还是四个？随着子计数的增加，虽然需要更多的比较来执行删除操作。树的高度可以降低更多的。我认为与二叉树实现相比，时间成本应该会显著降低的。
浏览 4提问于2010-10-10得票数 3
回答已采纳
3回答
堆排序是“分而治之”排序还是优先级队列排序？
另外，冒泡排序适合哪一类排序(除了可怕之外)。
我读到过堆排序通常被认为是一种“分而治之”的排序，但它也可以是优先级队列排序。严格来说是其中之一还是另一个？还是两者兼而有之呢？我找不到任何关于冒泡排序可以被考虑的东西。
浏览 2提问于2013-03-19得票数 3
回答已采纳
我已经搜索了很长一段时间了，但是我找不到visual c++对std::sort函数使用的算法，我知道GNU C++库使用Intro排序，但是似乎没有任何消息来源说明微软的可视c++使用哪一个！
浏览 9提问于2014-04-05得票数 5
回答已采纳
1回答
因此，我试图找出一些算法，这些算法以最类似于基于PQ的排序的方式进行，用于以下结构。
1堆
3堆
n-1堆
BST
平衡BST
例如堆排序和d堆。Heapsort使用2堆作为中间表示来对内容进行排序.对于堆排序，PQ是一个2堆，即使任何PQ都能工作。
浏览 0提问于2018-04-29得票数 0
我们得到了一个整数数组：
45, 10, 56, 42, 95, 78.
我们必须找到差异最小的两个元素。我在线性时间复杂度中做到了这一点，但它只在排序的顺序上工作，这总共导致了二次复杂度的运行时间。我们有什么方法可以在对数或线性时间复杂度下做到这一点吗？
提前谢谢。
浏览 0提问于2015-08-02得票数 3
1回答
堆排序的辅助空间与空间复杂度的差异？
我的尝试：
如所解释的
如果我们想比较基于空间的标准排序算法，那么辅助空间将是一个比空间复杂性更好的标准。合并排序使用O(n)辅助空间，插入排序和堆排序使用O(1)辅助空间。然而，所有这些排序算法的空间复杂度都是O(n)。
我搜索了堆排序的空间复杂性，发现空间复杂度是O(1)。
我的问题是：
这个解释正确吗？辅助空间和空间复杂性有什么区别？
浏览 4提问于2017-06-01得票数 3
回答已采纳
我不知道这个算法是堆排序还是快速排序.
假设我有一个没有源代码的算法--它是不稳定的，在大型数据集上性能很好，对于有序和无序的集合，运行时间类似。
如果没有更多的信息，是否可以判断这个算法是堆排序还是快速排序？
浏览 5提问于2016-06-21得票数 2
回答已采纳
1回答
我在一个项目中工作，我想使用堆排序对数据进行排序，因为最坏的情况对我的项目非常重要。我知道快速排序在平均情况下更快，但我不能在我的项目中使用它，因为o(n^2)最坏的情况。
我想知道有没有缓存效率高的堆可以用来进行堆排序，它的空间复杂度更低？我想知道缓存效率对堆排序和快速排序的影响？它对堆排序的影响有多大？是影响太大了还是可以忽略不计？
浏览 2提问于2014-02-16得票数 3
我在网上遇到了一个问题，询问从堆支持的Min优先级队列中获取最大值的平均时间复杂度。
我推断答案是O(n)，因为堆是由数组支持的，迭代数组一次以找到最大值需要进行n比较。
然而，答案是O(nlogn)。有谁能解释一下为什么会这样，为什么我的推理失败？
浏览 6提问于2017-12-11得票数 0
回答已采纳
1回答
我正在实现一个堆排序，我开始想知道堆的不同实现。当您不需要按索引访问元素时(就像在堆排序中一样)，使用数组实现堆或像其他链接数据结构一样实现堆有什么优缺点。
我认为重要的是要考虑到节点和指针所浪费的内存与数组中空格所浪费的内存，以及在必须调整数组大小时添加或删除元素所需的时间。
我应该在什么时候使用每一个，为什么？
浏览 2提问于2011-06-27得票数 0
回答已采纳
我使用堆函数对数组进行排序。
import heapq
arr =[-74, 0, -4, 20, 7, 1, -4700, 74, 21, 71000, 87, 400, 9]
print ("The array: ", arr)
print("")
heapArray = arr
length = len(arr)
heapq.heapify(heapArray)
sortedArray = []
for each in (arr[:length]):
sortedArray.append(heapq.heappop(heapArray))
浏览 9提问于2022-06-08得票数 -1
我遇到过这个问题，它要求计算一个算法的最坏情况下的运行时间，该算法与mergeSort非常相似，但两个递归调用中的一个被堆排序替代。
因此，我知道在mergesort中除以需要恒定的时间，并且合并是O(n)。堆排序采用O(nlogn)。这是我想出来的: T(n) = 2T(n/2) + O((n/2)logn)+ O(n)。我对O((n/2)logn)部分有一些疑问。是n还是n/2？我写了n/2，因为我只对数组的一半进行堆排序，但我不确定这是否正确
浏览 1提问于2019-03-31得票数 1
堆是适用以下条件的列表：
l[i] <= l[2*i] && l[i] <= [2*i+1]
对于0 <= i < len(list)
我在找就地排序。
浏览 1提问于2008-09-22得票数 2
回答已采纳
8回答
根据题目，如果数组的长度为奇数，并且数组元素的编号为1- 10。
例如，
3 6 8 1 3 7 7 9 4 1
我在考虑使用堆排序？由于它是一个数组，合并排序和插入排序需要移位，因此效率不高。
浏览 108提问于2011-09-29得票数 21
回答已采纳
3回答
我正在学习不同的排序算法及其时间/空间复杂度，并看到冒泡排序和插入排序等算法的空间复杂度为O(1)。
这让我感到奇怪，因为最低的空间复杂度肯定是O(n) (例如，存储数据集所需的内存，仅此而已)？
浏览 1提问于2017-05-10得票数 7
回答已采纳
4回答
在递归算法情况下计算时间复杂度？
、、、、
在使用递归算法的情况下如何计算时间复杂度？
例如t(n) = t(3n/2) + 0(1) (堆排序)
浏览 0提问于2011-11-02得票数 1
回答已采纳
2回答
空间复杂性混淆
、、、、
一般情况下，我对分析空间复杂性有点困惑。我不确定“算法占用的额外空间”是什么意思。什么是1的空格？在下面的示例中
int findMin(int[] x) {
int k = 0; int n = x.length;
for (int i = 1; i < n; i++) {
if (x[i] < x[k]) {
k = i;
}
}
return k;
}
空间复杂度为O( n )，我猜这是由于数组大小为n所致。
但是对于像heapsort这样的东西，它需要O(1)。就地堆排序
浏览 1提问于2012-12-27得票数 1
回答已采纳
1回答
合并排序和堆排序
、、、
假设您希望通过首先将Heap排序应用于多个连续的子数组来改进合并排序。给定数组A，您的算法将A细分为子数组A1，A2···Ak，其中k是2的幂，并单独对每个子数组Ai应用堆排序。该算法继续对连续子数组进行合并，直到对数组进行排序。例如，如果k= 4，则首先应用堆排序对每个Ai进行排序，然后将A1与A2合并，A3与A4合并，然后应用合并函数一次获得排序数组。(a)当k=2时，所提出的算法是否改善了合并排序的渐近运行时间？那么k= log n(或最接近log n的2的幂)如何？证明是正当的。(b)建议的算法是否稳定？它在原地吗？证明你的答案。
所以我有个问题要解决，我在想，对于k=2来说，阈值太低
浏览 1提问于2022-02-09得票数 0
2回答
请问使用O( arr2 (N))比较的排序方法是什么(例如:按排序顺序将未排序的arr1中的项排列到已排序的log(N)中)？
浏览 28提问于2020-10-13得票数 0
虽然我知道这似乎是显而易见的，但我会解释我的困惑。我一直认为快速排序的最坏情况时间复杂度是O(n^2)。[Arrays.sort(int[])]()从Java 7到Java 13的文档说:该算法在上提供O(n log(n))性能--许多数据集导致其他快速数据集退化为二次性能，并且通常比传统的(单轴)快速排序实现更快。
这里的关键字是“多”，所以我假设这里的O(n log(n))指的是平均情况，而且仍然存在导致O(n^2)最坏情况的数据集。
但是在Java14和更高版本中，[Arrays.sort(int[])]()的文档说:该算法在所有数据集上提供O(n (N))性能。
那么，对于现在改进的快
浏览 6提问于2022-03-16得票数 2
回答已采纳
1回答
堆排序的目的是什么？
、、、、
当我们构建堆时，数组中的元素会按照特定的顺序(升序或降序)排列，这取决于它是最大堆还是最小堆。那么，当构建堆本身以较低的时间复杂度按排序顺序排列元素时，堆排序的用途是什么？
void build_heap (int Arr[ ])
{
for(int i = N/2-1 ; i >= 0; i-- )
{
down_heapify (Arr, i, N);
}
}
void heap_sort(int Arr[], int N)
{
浏览 8提问于2021-09-05得票数 2
回答已采纳
1回答
我试图并行实现多个top-k选择，其中每个选择从n个元素列表中选择k个元素，这样的任务将并行执行。我用幼崽做的。我犯了一个奇怪的错误，我不知道我在哪里做错了。我觉得我在理解上可能犯了明显的错误，有人能帮我查一下吗？
编辑：
我在包含cudaDeviceSynchronize()的两个代码部分之前添加了两个free()调用，从而使其工作起来。现在我的问题是，free的行为是否与cudaFree不同，因为异步调用立即进行是不允许的，与我在这里提出的另一个问题相反：
// Assume dtop has size k x m and dmat has size n x m, where k <
浏览 1提问于2014-01-18得票数 0
回答已采纳
2回答
为什么在堆排序中使用平面列表？
、、、、
在heapsort中，数据存储在一个叫做“堆”的东西中。几乎我看到的所有实现都使用平面列表作为数据结构。
有人能给我解释一下为什么吗？
为什么不使用嵌套数组或二叉树的实例？明示不比内隐好吗？
是因为执行困难，比如遍历结构，还是其他原因？
浏览 0提问于2012-03-30得票数 0
回答已采纳
在CLRS书中，通过自顶向下的heapify构建堆具有O(n)的复杂性。堆也可以通过反复调用插入来构建，在最坏的情况下，插入的复杂性为nlg(n)。
我的问题是:为什么后一种方法的性能较差？
我问这个问题是因为我觉得数学背后有一些简单的见解。例如,
快速排序、合并排序和堆排序都是基于减少不必要的比较，但方法不同。快速排序:平衡分区，不需要比较左子集和右子集。合并排序:简单地比较两个子数组中的两个最小元素。堆排序:如果A的值大于B，则A的值比B的后代大，不需要与他们进行比较。
浏览 5提问于2014-01-29得票数 4
回答已采纳
1回答
如果我们使用的是顺序机器(不可能进行并行比较)，并且是按顺序进行比较，并且在对32个随机元素进行排序时，我们希望尽量减少处理器时钟周期的数目，那么我们应该使用排序网络还是自适应排序算法？
对于n=32元素，还没有最优网络。实际上，如果我们要最小化CPU时钟周期的数目，那么最好将32个元素划分为n=8的四个子列表，并在每个子列表上应用最优排序网络，然后将这些列表合并在一起吗？
很明显，我们在这里使用的是“平均性能”，因为如果给出一个已经排序的列表，自适应算法就会很幸运。
计算数字，我们有以下几个数字：
对大小n的列表进行排序：
n=2的最小比较数为1。
n=4的最小比较数为5。
n=
浏览 5提问于2018-04-26得票数 2
我有一个二维的p_q数组，我想对这个数组按m_n的二维数组进行排序，其中p>m和p=km，q>n和q=kn，以及k是整数。例如，我有一个16*16的数组，我把它划分为4*4的2d数组，现在我想独立地对这4*4数组进行排序。在不需要额外内存的情况下，我可以使用哪种算法在place.means中对这些数据进行排序。
浏览 9提问于2009-08-15得票数 0
2回答
可以使用堆排序排序的元素数？
、、、、
我在考试中遇到了一个非常令人困惑的问题，并且尝试错了，这是一个客观类型的问题，给出了四个选项，现在我知道正确的选项，但我没有任何解释。
问题:
可以在Ɵ(logn)时间内使用堆排序排序的元素数是
( a)Ɵ(1)
( b)Ɵ(√日志
( c)Ɵ(log / loglog n)
( d)Ɵ(log )
选项c是正确的.
我选择了选项a)，我认为在日志中只有一个元素会被排序，这是错误的，我不知道为什么选项c)是正确的。
浏览 6提问于2013-04-03得票数 2
回答已采纳
问题是：
以最小的时间复杂度将k排序数组与n个元素合并到一个大小为nk的数组中。该算法应该是一个基于比较的算法。不应对输入作出任何假设。
因此，我知道有一种解决nklogk时间复杂性问题的算法，如这里所提到的：。
不过，我的问题是，我们能不能比nklogk少排序，这意味着，运行时是o(nklogk)。
于是我在网上搜索并找到了这样的答案：
它声称将一个大小为K的数组划分为单个数组，并将它们合并到一个数组中。但是这是不正确的，因为人们可以说他找到了一种解决sqrt(n)klogk问题的算法，即o(nklogk)但是n=1，所以我们在KlogK时间对数组进行排序，这与数组排序的下限并不矛盾
浏览 5提问于2022-05-22得票数 0
1回答
堆排序工作99%
、、
我想知道我是否可以得到一些堆排序实现的快速帮助。对我哪里出了问题有什么建议吗？以下是我的源代码：
code removed, problem was solved!
谢谢你们！
浏览 2提问于2012-12-05得票数 1
回答已采纳
2回答
堆排序时间复杂度深入理解
、、、、
当我在大学学习数据结构课程时，我学到了以下公理：
在最坏的情况下，向堆中插入一个新的数字需要O(logn) (取决于它作为叶子插入到树中的高度)
使用从空堆开始的n插入构建一个由n节点组成的堆，并使用摊销分析将其求和为O(n) time
在最坏的情况下，删除最小的O(logn)时间(取决于新的顶节点在与最后一个叶子交换后到达的最低程度)。
将所有最小值逐个移除，直到堆为空，需要O(nlogn)时间复杂度。
提醒：“堆排序”算法的步骤是：
将所有数组值添加到堆中:使用摊销分析技巧将其相加为O(n)时间复杂度
从堆n时间中取出最小值，并将
浏览 4提问于2015-08-20得票数 3
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
