プログラマ専用SNS ミクプラ

N分ヒープによってデータを格納する際に、そのデータをすでに格納されているデータと大きさを比較した回数を返す関数を作りたいのですが、よくわかりません。どうしたらよいでしょうか？

コード:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 5000000

int A[N];
int B[N];

int insert_n_heap(int d,int n){
  int i=N-1;
  long count=0;
  A[N-1]=d;
  while(i!=0){
    if(A[i]<=A[(i-1)/n]){
      A[i]=A[(i-1)/n];
      A[(i-1)/n]=d;
      count++;
    }
      i=(i-1)/n;
      count++;
  }
  return count;
}
int main(void){
  int i,j;
  long result;
  clock_t start,end;
  int a;

  for(a=0;a<N;a++){
    A[a]=0;
  }
  srand((unsigned)time(NULL));
  for(i=0;i<N;i++){
    B[i]=rand();
  }
  start=clock();
  for(j=0;j<N;j++){
    result+=insert_n_heap(B[j],2);
  }
  end=clock();

  printf("Tins=%f sec\n",(double)(end-start)/CLOCKS_PER_SEC);
  printf("Cins=%ld\n",result);
  return 0;
}

パッと見で返信してしまいますが result の初期値を 0 にし忘れてるという事ではないですか。
あと insert_n_heap の while ループ内、if の条件に合致すると count が2回インクリメントされる気がしますが大丈夫でしょうか。

プログラマ専用SNS ミクプラ

N分ヒープについて

N分ヒープについて

Re: N分ヒープについて