- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我从以下位置找到了堆排序的代码:http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#C
我的理解方式(这在某些地方是错误的)是 heapsort() 函数有两个循环。第一个循环是创建堆结构(最小或最大),第二个循环是对 double 进行实际排序。但我认为我的第一个循环是错误的。
整个代码是这样的
#include <stdio.h>
#include <stdlib.h>
#define ValType double
#define IS_LESS(v1, v2) (v1 < v2)
void siftDown( ValType *a, int start, int count);
#define SWAP(r,s) do{ValType t=r; r=s; s=t; } while(0)
void heapsort( ValType *a, int count)
{
int start, end;
/* heapify */
for (start = (count-2)/2; start >=0; start--) {
siftDown( a, start, count);
}
for (end=count-1; end > 0; end--) {
SWAP(a[end],a[0]);
siftDown(a, 0, end);
}
}
void siftDown( ValType *a, int start, int end)
{
int root = start;
while ( root*2+1 < end ) {
int child = 2*root + 1;
if ((child + 1 < end) && IS_LESS(a[child],a[child+1])) {
child += 1;
}
if (IS_LESS(a[root], a[child])) {
SWAP( a[child], a[root] );
root = child;
}
else
return;
}
}
int main()
{
int ix;
double valsToSort[] = {
1.4, 50.2, 5.11, -1.55, 301.521, 0.3301, 40.17,
-18.0, 88.1, 30.44, -37.2, 3012.0, 49.2};
#define VSIZE (sizeof(valsToSort)/sizeof(valsToSort[0]))
heapsort(valsToSort, VSIZE);
printf("{");
for (ix=0; ix<VSIZE; ix++) printf(" %.3f ", valsToSort[ix]);
printf("}\n");
return 0;
}
我的问题是,为什么/heapify/循环从 (count-2)/2 开始?
此处来自 heapsort() 的片段:
/* heapify */
for (start = (count-2)/2; start >=0; start--) {
siftDown( a, start, count);
}
更新
我想我可能刚刚回答了我自己的问题,但这是因为我们必须建立一个堆结构,其中循环的部分重点是创建平衡树吗?也就是说,堆必须填满除最后一层之外的每一层。这是正确的想法吗?
最佳答案
对于奇数计数,heapify 的第一个子对是 a[((count-2)/2)*2 + 1] 和 a[((count-2)/2)*2 + 2],最后一个数组的两个元素。对于偶数计数,单独的子元素位于数组的最后一个元素 a[((count-2)/2)*2 + 1] 处。这是堆化整个数组的起点。第二个循环只需随着 end 的减少而重新堆化大部分堆化的数组 [0 到 end]。
维基文章:
关于c - 堆排序 heapify,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34111120/
我正在尝试构建一个最小堆,但未能获得正确的结果。我不确定可能出了什么问题。 输入 = 209 97 298 54 110 27 250 455 139 181 446 206 478 90 88 输出
我从以下位置找到了堆排序的代码:http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#C 我的理解方式(这在某些地方是错误的)是 heapso
下面是堆类。我正在尝试对堆进行排序,但我的 max_heapify 函数有问题。我插入了值 [10, 9, 7, 6, 5, 4, 3] 并且我的堆排序打印给定的输出。给定的输出和期望的输出在类下面给
我正在学习一门关于数据结构和算法的类(class),我应该在其中实现堆排序算法以在指定的时间范围内运行。下面是两个实现: def generateSwaps(): size=self._n f
def heapify(A): for root in xrange(len(A)//2-1, -1, -1): rootVal = A[root] child
我想插入一些节点,看来这个功能有问题。可以插入但不能执行heapify。我想知道添加新元素后索引是否困惑。欢迎任何评论。谢谢。 def heapify(arr, n, i): smallest
这是我最近遇到的面试问题之一。 给定完整或几乎完整二叉树的根地址,我们必须编写一个函数将树转换为最大堆。 这里不涉及数组。树已经构建完毕。 例如, 1
我有一个关于堆排序的问题。我不知道我的代码有什么问题。该程序仅更改了表中的第二个和最后一个位置。这是我的代码(没有主要功能): #include #define DUZO 100000000 i
我正在尝试制作一种适用于我的自定义容器的自定义(而不是使用 STL 方法)堆排序方法。我有迭代器,但是我找不到 make_heap 算法的描述。据我所知,它的作用类似于排列元素,使它们看起来像一个二叉
问题是我正在尝试修复最大堆,但它不起作用,因为错误不断发生。我一直在遵循几本书中的伪代码,但仍然显示错误。我尝试使用 = 进行交换,将 A[i] 交换为 A[largest],但出现错误 class
一旦调用了remove min函数,我如何在java中“堆化”基于数组的最小堆(这只是获取索引1处的元素并将其删除,然后用数组中的最后一项替换它)。我很困惑在删除最小值发生后如何将数组再次放入最小堆中
每次 heapq.heapify 函数更改我的堆列表中的元素时,我都希望得到回调通知(顺便说一句,这是跟踪列表中的对象以及它们的索引如何获取所需要的改变了)。 我的计划是从 list 继承并重写 __
Tarjan 的“数据结构和网络算法”在 leftiest heaps 中陈述了 heapify 函数如下: heap function heapify (list q); do |q| ≥ 2
我试着看http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-alg
我正在用 Ruby 实现 Heapify 算法(即将二叉树转换为堆),并认为下面的算法有效。我担心的是我进行了过多的递归调用。 第一次和第二次递归调用是从左右子树中选择最高节点,第三次递归调用是在我交
我一直在研究算法入门教科书中的一些算法,特别是我正在尝试让二叉堆 100% 正确地工作。我有一种奇怪的感觉,我正在使用的示例不正确,我想知道是否有人可以帮助我指明正确的方向。 给定数组 int[ ]
我对最大堆排序伪代码的一部分感到困惑。下降到 2 是什么意思? HeapSort(A) Build-Max-Heap(A) for i down to 2 do exchange A[1] A[i]
在CLRS书中,自上而下的heapify构建堆的复杂度为O(n)。也可以通过反复调用插入来建立堆,其最坏情况下的复杂度为nlg(n)。 我的问题是:对于后一种方法性能较差的原因,是否有任何见解? 我问
我有 b = heapify([5,4,9,1]) 如果我做一个 type(b) 它说它是 NoneType 而不是列表类型,有人知道我做错了什么吗?? 最佳答案 heapify() 方法就地转换列表
我正在为计算机科学类(class)创建一个堆实现,我想知道下面的递归函数是否会从一个还不是堆的数组对象中创建一个堆。代码如下: void Heap::Heapify(int i) { int
我是一名优秀的程序员,十分优秀!