通过数组实现遇到Downheap算法问题

我目前正在尝试使用Down-heap算法对我的数组进行排序。但是，当我显示新排序的数组时，会出现新的数字，并且顺序看起来不正确。我不知道我的算法是否有问题，或者我没有使用这种排序算法的适当条件。通过数组实现遇到Downheap算法问题

我的工作是对20个键的数组进行排序。

的代码：

/* Downheap sorting algorithm */ 
for(i=0; i<20; i++) 
{ 
    j = i + 1; 

    /* If parent is less than both children */ 
    if(key[j] < key[2*j] && key[j] < key[(2*j)+1]) 
    { 
     /* Check which child is smallest */ 
     if(key[2*j] < key[(2*j)+1]) 
     { 
      /* Parent is assigned smallest node */ 
      swap(&key[j],&key[2*j]); 
     } 
     else{swap(&key[j],&key[(2*j)+1]);} 
    } 

    /* If parent is less than left child */ 
    else if(key[j] < key[2*j]) 
    { 
     swap(&key[j],&key[2*j]); 
    } 

    /* If parent is less than right child */ 
    else if(key[j] < key[(2*j)+1]) 
    { 
     swap(&key[j],&key[(2*j)+1]); 
    } 
}

交换函数：

void swap(int *parent, int *child) 
{ 
    int temp; 
    temp = *child; 
    *child = *parent; 
    *parent = temp; 
}

键的阵列之前排序：

54,90,137,260,185,65,208,139,114,176,186,77,137,139,178,57,203,110,80,127

阵列键排序后的一次：

54,137,185,260,114,77,208,178,110,176,186,65,137,139,139,64,203,90,84,127

64是不存在之前。 57在哪里？ 80消失了，84从哪里来？

任何帮助将不胜感激！

来源

2014-11-03 Plaidypus

您可能想要检查循环的终止条件：定义了多少个数组元素，ond（2 * j）+ 1'get有多大？ – greybeard 2014-11-03 08:04:16

事实证明，我的文件（我没有提及我从一个文件中读取这些数字，显示为20x10矩阵）在每行的末尾有额外的空格。我解决了这个问题，算法运行得很好。 – Plaidypus 2014-11-04 05:13:04

对于一个测试，使数组大两倍+ 1，并在读入之前用键的最小值和最大值进行初始化（即使看到您接受了解决同一问题的答案）。 – greybeard 2014-11-04 05:29:17

如果您有一个由20个数组组成的数组，它们通常是key [0] ... key [19]，并且需要考虑堆中一个或多个子元素不存在的可能性，因为他们的数组位置会离开阵列的边缘。随着堆数0..19，那么元素i的孩子将在2i + 1和2i + 2，所以0有孩子1和2,1有孩子3和4 ... 8有孩子17和18，但9 19岁时只有一个孩子，10个孩子根本没有孩子。

您是否期待Downheap执行所有排序工作？通常，如http://en.wikipedia.org/wiki/Heapsort所述，Downheap是Heapsort的一部分，但不是全部。

来源

2014-11-03 05:53:06 mcdowella

Woops。好像我错过了那堂课！我会检查链接并尝试将它们放在一起。谢谢！ – Plaidypus 2014-11-03 06:09:21

通过 “DownHeap” 我asuming你的意思是最小堆

算法中的最小堆：

public void insert(Comparable x) { if(size == heap.length - 1) doubleSize();

//Insert a new item to the end of the array 
int pos = ++size; 

//Percolate up 
for(; pos > 1 && x.compareTo(heap[pos/2]) < 0; pos = pos/2) 
    heap[pos] = heap[pos/2]; 

heap[pos] = x;

}”

检查此链接了解最小堆min heap

来源

2014-11-03 05:50:16

通过数组实现遇到Downheap算法问题

回答

相关问题