您好，我这里的问题是伪code有关筛选和筛选下来堆 [英] hi i have question here is pseudo code about sift up and sift down on heaps

问题描述

我有以下伪code：

 无效siftup（INT N）
 pre条件N＆GT; 0安培;＆安培;堆（1，N-1）
后堆（1，N）
 I = N;
 循环
/ *不变：堆（1，N）也许除了
  我与其父之间
 如果（ⅰ== 1）
   打破;
 P = I / 2;
 如果（X [P]＆其中; = X [i]于）
   打破;
 掉期（P，I）;
我= P;
 

请帮我在现实$ C $词写有关于循环，例如，其中的问题是起点循环？

我已经DOEN这是正确的吗？ 公共类siftup {

公共静态无效的主要（字串[] args） {

INT磷;

INT N = 12; 诠释一个[] =新的INT [] {15,20,12,29,23,17,22,35,40,26,51,19};

INT I = N-1;  而（ⅰ！= 0） {

如果（我== 1）  打破;

P = I / 2;  如果（一个[P]其中; = A [1]）{  诠释T =一[P]。 一个[P] = A [1]; A [1] = T; } 我= P;

}

有关（INT J = 0;Ĵ

} } //结果是这样的 15 20 19 29 23 12 22 35 40 26 51 17

解决方案

如果 ^ h 是堆，是一个最大堆，其索引从0和ñ是元素的数量，那么这应该工作：

  INT位置= N  -  1;
而（仓位大于0和放大器;＆放大器; H [（位置 -  1）/ 2]其中= H [位置]）//而当前节点的父是比目前孩子小，换用其子（仅在一个最大堆，它的周围的其他方法的最小堆）
{
    掉期（H [（位置 -  1）/ 2] = H [位置]）;
    poistion =（位置 -  1）/ 2;
}
 

  

我有关于循环，例如，其中的问题是起点循环？

循环开始堆数组的最后一个元素，因为这通常是要移动到合适的位置之一。

i have following pseudo code :

void siftup(int n)
 pre condition n>0  && heap(1,n-1)
post heap(1,n)
 i=n;
 loop
/* invariant: heap(1,n)   except  perhaps 
  between    i and   its parent 
 if (i==1)
   break;
 p=i/2;
 if (x[p]<=x[i])
   break;
 swap(p,i);
i=p;

please help me to write it in real code i have question about loop for example where is starting point of loop?

i have doen this and is it correct? public class siftup {

public static void main(String[]args) {

int p;

int n=12; int a[]=new int[]{15,20,12,29,23,17,22,35,40,26,51,19};

int i=n-1; while (i!=0) {

if (i==1) break;

p=i/2; if (a[p]<=a[i]){ int t=a[p]; a[p]=a[i]; a[i]=t; } i=p;

}

for (int j=0;j

} } //result is this 15 20 19 29 23 12 22 35 40 26 51 17

解决方案

If h is your heap and is a max-heap, its indexed from 0, and n is the number of elements, then this should work:

int position = n - 1;
while (position > 0 && h[(position - 1) / 2] <= h[position]) // while the parent of the current node is smaller than the current child, swap it with its child (only in case of a max-heap, it's the other way around for a min-heap)
{
    swap(h[(position - 1) / 2] = h[position]);
    poistion = (position - 1) / 2;
}

i have question about loop for example where is starting point of loop?

The loop starts with the last element of the heap array, as that is usually the one you want to move to the right position.

这篇关于您好，我这里的问题是伪code有关筛选和筛选下来堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！