ヒープソートでなぜ再帰？
〜日本語版ウィキペディアの問題点と最強最速のヒープソート〜
最近ヒープソートを作らせてみると、再帰を使ったヒープソートが出てくることが多い。
再帰を使ったヒープソートは考え方が単純でわかりやすい。
けれど、ヒープソートでの繰り返しは、あらかじめ決まった回数を繰り返すため、再帰の必要性はない。
普通にループ処理をした方が圧倒的に速いし、スタックのオーバーフローの心配も少ない。
クイックソートのように何回繰り返すか分からないような場合は再帰がベストだし、再帰しか方法がないようなケースもあるが、再帰は呼び出す前の関数の状態を保持するため、あっという間にスタックのオーバーフローを引き起こす。
LinuxであればWindowsの10倍程度の再帰に対するスタックメモリ耐性を持つが、それでも遅くなることは間違いないし、かなりのスタックメモリを消費する。
ヒープソートでなぜ再帰？
その答えは簡単にわかった。
原因は「ウィキペディア（Wikipedia）」である。
ウィキペディアのヒープソートの解説やそこにある疑似言語で再起型のヒープソートのみが紹介されているのである。（現在は非再帰型も紹介されるようになった）
それもめちゃめちゃ効率が悪いヒープソートである。
英語版のWikipediaの方はかなり効率の良いヒープソートがＣ言語で紹介されているものの、そこまで見るものは少ないし、それでもまだ随分非効率なところがある。
そして、ウィキペディアを書き換えようかと思ったが、とても面倒なのでこちらにて問題提起することにした。
暗黙のうちにウィキペディア信者になってしまっている者がたくさんいることを思うと確かに怖い問題である。
そもそも「for」という命令の存在理由を考えれば、「回数の決まった繰り返し処理」を意識しプログラミングをすべきである。
「for」などなくてもすべてのプログラムは書けるが、それでも「for」は存在しプログラマに暗に「回数の決まった繰り返し処理」の存在を明示しているのである。
下手な「while」の使い方をするのなら、「for」の方が高速に処理できるようコンパイルされるケースも多い。（正しく「while」を使えばほぼ確実に「for」より速いが）
ということで、たまたま今から作るプログラムの一部が「回数の決まった繰り返し処理」であれば、それを意識して「高速」かつ「負荷が少なく」かつ「メモリ
使用量も少ない」プログラミングをすべしである。（ケースによって「高速」優先であったり、「メモリ使用量最小」優先であったりするが）
再起を覚えたからといって、無理に使う必要はないのである。
ディレクトリ階層を追っかけるプログラムなど、どうしても再帰に頼らざるを得ないケースもあるのだから、そんなときこそ再帰である。
安易に答えを載せることは好ましくないのは確かだが、このままでは携帯電話のようにガラパゴス状態となり、日本だけ再帰型ヒープソートを使う国になってし
まう恐れもあるため、僭越ながら私が作ったヒープソートのコードを掲載することにした。
作った時期がバラバラなので、統一感のないコードになってしまっているが、そこは寛大にご了承願いたい。
今のところ、これ以上高速なヒープソートは考えられないものとして作ったつもりなので、もしこれを超える速度のヒープソート（コンパイルオプションを変え
れば？とかなしね）がありましたら、ご教示願いたい。
ただし、CPUやOS、仮想化の種類など環境によって私の想定した通りの結果が出ない場合もあるので、その点はご了承願いたい。
また、もしも思いっきりバグっていたらお叱りのお言葉をお願いしたい。
いらないかもしれないけれど、答えを証明するために時間計測できるよう、まずは、gettime関数を記載したgettime.h。
★時間計測用ヘッダファイル
１、２行目はLinux、Windows好きな方（使っているＯＳ）を選ぶ。
下の４つのヒープソートとも使いますので、ファイル名など気をつけてください。
ファイル名：<gettime.h>
#define Linux
//#define Windows
// ★ Windows 用 gettime
#ifdef Windows
#include <stdlib.h>
#include <time.h>
#include <windows.h>
double gettime(void);
double gettime(){
LARGE_INTEGER f,n;
memset(&f,0x00,sizeof f);
memset(&n,0x00,sizeof n);
QueryPerformanceFrequency(&f);
QueryPerformanceCounter(&n);
return (double)n.QuadPart/f.QuadPart;
}
#endif
// ★ Linux 用 gettime
#ifdef Linux
#include <stdlib.h>
#include <time.h>
double gettime(void);
double gettime(){
struct timeval tv;
gettimeofday(&tv,NULL);
return tv.tv_sec+(double)tv.tv_usec*1e-6;
}
#endif
★ヒープソート１（日本語ウィキペディア解説バージョン）
劇的に遅いし、劇的に効率が悪いので利用しないでください。
//日本語Wikipedia解説バージョン ヒープソート
//日本語Wikipedia解説バージョンは単純で解りやすい（？）が桁違いにロスが多すぎるため、絶対に参考にしないこと
#include <stdio.h>
#include "gettime.h"
#define DC 20000 //データの件数（日本語Wikipedia解説バージョンは劇的に遅すぎるため、最大20,000件まで）
int dc;
void swap(int *dat,int d1,int d2){
int w;
w=dat[d1];
dat[d1]=dat[d2];
dat[d2]=w;
}
void make_heap(int *dat,int oya){
int dko;
int lko;
int rko;
lko=(oya+1)*2-1; //wikiは配列添え字を1から数えているので0からの添え字対応に変更
rko=lko+1;
if(lko>dc)return; //子がないなら戻る
if(lko==dc){ //添え字の最後が左の子の場合
if(dat[lko]>dat[oya])swap(dat,lko,oya); //左の子の方が親より大きい場合入れ替え
return;
}
make_heap(dat,lko); //左の子をヒープソートにかける（ヒープな構成が完成していればいらない）
make_heap(dat,rko); //右の子をヒープソートにかける（ヒープな構成が完成していればいらない）
if(dat[lko]>dat[rko]){ //左の子の方が右の子より大きい場合
dko=lko; //交換候補を左の子とする
}else{ //そうでない場合
dko=rko; //交換候補を右の子とする
}
if(dat[oya]<dat[dko]){ //親より交換候補の子の方が大きい場合
swap(dat,oya,dko); //親と交換候補の子を入れ替え
make_heap(dat,dko); //入れ替えた子を親にしてヒープソートにかける
}
}
void heap(int *dat){
while(dc>0){ //ここは(int)dc/2+1で充分に思われる。というのもそれより大きな値では親になれないから
make_heap(dat,0); //いきなりの「ヒープの再構成方式」で、無理やり「ヒープの構成」をしようとするためロスがでる
swap(dat,0,dc); //入れ替え
dc--; //最後の添え字を一つ前に
}
}
int main(){
int i; //ループ制御変数
int dat[DC+1]; //データ格納用配列
double st; //開始時刻（Start Timeの略）
double pt; //処理時間（Processing Timeの略）
dc=DC-1;
srand((unsigned)time(NULL)); //乱数ジェネレータの初期化
for(i=0;i<DC;i++)dat[i]=rand()%32768; //0〜32,767の乱数を生成し配列に格納
st=gettime(); //開始時刻の取得
heap(dat); //ヒープソート関数呼び出し
pt=(gettime()-st)*1000; //処理時間の計算
// for(i=0;i<DC;i++)printf("%d¥n",dat[i]); //処理結果の表示
printf("処理時間： %10.4f ミリ秒¥n",pt); //処理時間の表示
return 0;
}
★ヒープソート２（英語版ウィキペディアのDreamHope風改変バージョン 高速ヒープソート）
これはそこそこのスピードがでます。
//英語版WikipediaのDreamHope風改変バージョン 高速ヒープソート
#include <stdio.h>
#include "gettime.h"
#define DC 200000 //データ数（Data Countの略）
void ReComposition(int *dt,int dc,int ss,int dv){//ポイントとしては、Swap排除は元より、できる限り乗算除算を排除
int ch; //子の添字（Childの略）
int gp; //親の親の添字（Grand Parentの略）
int pt=ss; //親の添字として代入2（Parentの略）
//ヒープの再構成（退避したデータ（dv）抜きで）
for(ch=pt+pt;ch<dc;ch+=ch){ //最初の左の子から、最後の子より一つ前まで、次の左の子になるよう増分しながら繰り返す
if (dt[ch]<dt[ch+1])ch++; //右の子の方が大きければ対象を右の子に変更
dt[pt]=dt[ch]; //親のエリアへ対象の子の値を移動
pt=ch; //親の添字のエリアへ対象の子の添字を代入
}
if(ch==dc){ //左の子しかない場合
dt[pt]=dt[ch]; //親のエリアへ左の子の値を移動
pt=ch; //親の添字のエリアへ左の子の添字を代入
}
//退避したデータ（dv）の組み込み
while(((gp=pt/2)>=ss)&&dt[gp]<dv){ //親の親の添字が最初の親の添字以上か、またはその値が退避したデータ（dv）より小さい間繰り返す
dt[pt]=dt[gp]; //親のエリアへ親の親の値を移動
pt=gp; //親の添字のエリアへ親の親の添字を代入
}
dt[pt]=dv; //退避したデータの代入
}
void HeapSort(int *dt,int dc){ //*dtはデータ格納領域を指し示すポインタ、dcはデータ数（Data Countの略）
int ss; //添字（Subscriptの略）
int dv; //データの値（Data Valueの略）
if(dc<=1)return; //データ数が１個以下なら戻る
dt--; //添字を「０からデータ数-1」の範囲ではなく、「１からデータ数」までの範囲で利用できるようにする
//ヒープの構成
for(ss=dc/2;ss>0;ss--){ //最後の親の添字から最初の親の添字まで繰り返す
dv=dt[ss]; //親の値を退避（入れ替え回数を減らすため）
ReComposition(dt,dc,ss,dv); //親の添字のエリアからヒープの再構成にかける
}
//入れ替えとヒープの再構成
for(ss=dc-1;ss>0;ss--){ //最後より一つ前の子の添字から、最初の
dv=dt[ss+1]; //ヒープの再構成にかける値を退避（入れ替え回数を減らすため）
dt[ss+1]=dt[1]; //その時点での最大値を、その時点での最後の添字のエリアへ代入（移動）
ReComposition(dt,ss,1,dv); //１番の添字のエリアからヒープの再構成にかける
}
}
int main(){
int i; //ループ用制御変数
int dt[DC+1]; //データ格納用配列（Dataの略）
double st; //開始時刻（Start Timeの略）
double pt; //処理時間（Processing Timeの略）
srand((unsigned)time(NULL)); //乱数ジェネレータの初期化
for(i=0;i<DC;i++)dt[i]=rand()%32768; //0〜32,767の乱数を生成し配列に格納
st=gettime(); //開始時刻の取得
HeapSort(dt,DC); //ヒープソート関数呼び出し
pt=(gettime()-st)*1000; //処理時間の計算
// for(i=0;i<DC;i++)printf("%d¥n",dt[i]); //処理結果の表示
printf("処理時間： %10.4f ミリ秒¥n",pt); //処理時間の表示
return 0;
}
★ヒープソート３（DreamHopeオリジナルバージョン 爆速ヒープソート）
素晴らしい速度がでます。
//DreamHopeオリジナル 爆速ヒープソート（再帰を使わないヒープソート）
#include <stdio.h>
#include "gettime.h"
#define DC 200000 //データの件数
int main(){
int i; //制御変数
int oya; //親の添え字
int osh; //親の添え字保存
int oah; //親の値保存
int ko; //子の添え字
int dc; //データ数
int dat[DC+1]; //データ格納用配列
double st; //開始時刻（Start Timeの略）
double pt; //処理時間（Processing Timeの略）
srand((unsigned)time(NULL)); //乱数ジェネレータの初期化
for(i=0;i<DC;i++)dat[i]=rand()%32768; //0〜32,767の乱数を生成し配列に格納
st=gettime(); //開始時刻の取得
dc=DC;
//ヒープの構成
for(oya=(int)((dc-2)/2);oya>=0;oya--){ //最後の親から最初の親まで繰り返し
osh=oya; //親の添え字を保存
oah=dat[osh]; //親の値を保存
ko=osh+osh+1; //左の子の添え字を計算
while(ko<dc){ //子の添え字がデータ数以下の場合繰り返し
if(ko<dc-1 && dat[ko]<dat[ko+1])ko++; //入れ替え対象の添え字を右の子の添え字に変更
if(oah>=dat[ko])break; //親の保存値の方が子の値より大きい場合はループから抜ける
dat[osh]=dat[ko]; //子の値を親の添え字の位置へ代入
osh=ko; //その時の子の添え字を親の添え字とする
ko=osh+osh+1; //この時の子の添え字を計算
}
dat[osh]=oah; //保存しておいた親の値を代入
}
//ヒープの再構成
while(dc>0){ //添え字の最後から最初まで繰り返し
dc--; //添え字のデクリメント（これを最初に実行することで上記を成立）
osh=0; //親の添え字として0を代入
oah=dat[dc]; //最後の添え字の値を親の値として保存
dat[dc]=dat[0]; //最大値を最後の添え字のエリアへ代入
ko=osh+osh+1; //左の子の添え字を計算
while(ko<dc){ //子の添え字がデータ数以下の場合繰り返し
if(ko<dc-1 && dat[ko]<dat[ko+1])ko++; //入れ替え対象の添え字を右の子の添え字に変更
if(oah>=dat[ko])break; //親の保存値の方が子の値より大きい場合はループから抜ける
dat[osh]=dat[ko]; //子の値を親の添え字の位置へ代入
osh=ko; //その時の子の添え字を親の添え字とする
ko=osh+osh+1; //この時の子の添え字を計算
}
dat[osh]=oah; //保存しておいた親の値を代入
}
pt=(gettime()-st)*1000; //処理時間の計算
// for(i=0;i<DC;i++)printf("%d¥n",dat[i]); //処理結果の表示
printf("処理時間： %10.4f ミリ秒¥n",pt); //処理時間の表示
return 0;
}
★ヒープソート４（DreamHopeオリジナル神速バージョン 神速ヒープソート）
現在のところ最強です。
2009/11/16にWindows環境でもテストをしてみたところ、Windows BCC環境においてはシフト演算が遅いらしく、ko=osh<<1のところをko=osh+oshにしたほうが幾分高速でした。
同じコンピュータ環境で、Linux GCC環境では2,500,000件程度のデータを取り扱いできるのに対し、Windows BCC環境ではその10分の１の258,000件程度が最大です。
LinuxがWindowsよりも10倍性能が良いのか、GCCがBCCより10倍性能が良いのかはわかりませんが、この性能差には驚きました。
速度的にも同じデータ量で比較すると、Linuxが6msに対しWindows2000やWindowsXPで32msと5倍以上の遅さです。
もっと驚いたことは、Visual Studioでコンパイルすると、BCCと比較して更に取り扱いデータ量も減るし、速度が半分以下の速度しか出ません。
Microsoftが作ったVisual Studioなのに、さらにWindows上で取り扱っているのに、とても性能の悪いコンパイラで驚きました。
具体的には、BCCで32msに対し、Visual Studio（Releaseビルド時）で70ms程度の結果です。
Windows Vistaは話にならないほどひどいOSなので除外しますが、Windows 7でも2000やXPより更に遅くなります。
何故、高いお金を出してまでわざわざ遅いOSを購入する必要があるでしょうか。。。
Microsoftのプラットフォームである、Windows上において、Internet ExplorerがApple SafariやGoogle Chromeの数十倍遅いという結果と同様に、コンパイラにおいても15万円もするVisual Studioが無料のBCCの半分の速度も出ないほど完膚なきまでに負けているのです。
さらに、数万円するWindowsが無料のLinuxにメモリ許容量や速度面におけるアプリケーションプラットフォームとして完全に負けているのです。
力のある技術者は完全にMicrosoftから離れてしまったのでしょうか。。。
Visual Studioだけでなく、Windowsの寿命も、その先にはMicrosoftの寿命も見えたような残念な気分です。
「Linux & GCC」というOSS軍団に対して、「Windows & Visual Studio」のMicrosoft軍団はメモリ許容量でも、速度でも１０分の１の性能しか出せません。
これでも、あなたはMicrosoft WindowsやVisual Studioを使いますか？
CPU周波数が２倍の製品を購入しようとすると、下手をすれば10倍の金額差があります。8倍換算で1000倍です。
同じ性能を出そうと思ったら1000倍以上の金額が必要という考え方も否定できません。
OS&コンパイラ性能差が10倍で遅い方が約17万円するのに対して、早いほうが無料なのです。
本当に、これでも、あなたはMicrosoft WindowsやVisual Studioを使い続けますか？
試した私も驚きで一杯ですが、事実は認めざるを得ないので、現時点においてはLinuxを応援せざるを得ません。
サーバも同様なのです。
現時点でWindows ServerがUnix系サーバよりもシェアが広いのが現実です。
確かに優れたインターフェイスのWindowsは簡単に気持ちよく操作できますので、業務遂行の手助けになる部分も多々あるのは認めますが、500円で
売っているような中古マシンにLinuxを導入しサーバ化できるのなら、最新サーバマシンをWindowsでサーバ化する程度の性能を出せる可能性がある
のですから、少し落ち着いて考えてみる必要がありそうです。
ついでにMacのことも話してみますが、BSDベースの良いOSだと思います。
特にユーザインターフェースに関してはさすがAppleです。
Microsoftに追従を許さない、素晴らしいユーザインターフェイスです。
おまけに、Webkit（Safari）にも感謝です。
Microsoftの土俵（Windows上）で、当時のInternet Explorer 6に100倍程度の速度差を出して、Microsoftの技術力の低さを大々的に宣伝してくれました。
それで目の覚めたユーザも沢山います。
ただ、私はハードウェアは４万円以下、ソフトウェアというものは原則無料がベストと考えていますので、ハードもOSもMacにはなかなか縁がありません。
無料でもらった、古ーい昔のMac（Mac OS 9です）は今でもありますが、当分これからも縁はなさそうです。
こういった事実がわかってくれば、やがては本来なるべき姿になるのでしょう。
長いMicrosoft天下が続いてしまいましたが、これからは庶民の時代です。
OSSで活躍している庶民の方々が少しでも裕福になれるよう、MicrosoftのOSを買うくらいならLinuxにして、浮いたお金を募金でもしてください。
話が長くなりましたが、最強のヒープソートです！
未だこれを超えたというご報告をいただけていませんので、きっと最強なのでしょうが、アルゴリズムを必死で考えたり、高速なマシンを購入するくらいなら
OSをWindowsからLinuxに変えることのほうが遥かに高速だという前提での紹介ですので、それほどたいしたことでもありませんが、相当頑張りましたので見てやってください。（それでも日本のWikipediaで紹介されているヒープソートのバージョンと比べるなら数百倍は高速だとは思います）
| OS | 限界データ量 | 200,000件での実行速度 |
| Linux(Ubuntu 9.10 Desktop) & GCC | 2,500,000以上 | 6ms |
| Windows2000 & XP & BCC | 258,000程度 | 32ms |
| Windows2000 & XP & Visual Studio C++ | 250,000未満 | 70ms |
| Windows7 & BCC | 258,000程度 | 38ms |
| Windoes7 & Visual Studio C++ | 250,000未満 | 87ms |
DreamHopeの神速ヒープソートを超える、超神速ヒープソートの登場を期待する！//DreamHopeオリジナル 神速ヒープソート（再帰を使わない番兵型ヒープソート）
#include <stdio.h>
#include "gettime.h"
#define DC 200000 //データの件数
int main(){
int i; //制御変数
int d=0; //ソート結果検証用ダミー変数
int ng=0; //ソート結果NGカウンタ
int oya; //親の添え字
int osh; //親の添え字保存
int oah; //親の値保存
int ko; //子の添え字
int dc=DC; //番兵法で利用するデータ数
int dt[DC+2]; //データ格納用配列
int *dat; //データアクセス用ポインタ
double st; //開始時刻（Start Timeの略）
double pt; //処理時間（Processing Timeの略）
srand((unsigned)time(NULL)); //乱数ジェネレータの初期化
for(i=0;i<DC;i++)dt[i]=rand()%32768; //0〜32,767の乱数を生成し配列に格納
if(dc%2==1){ //右の子が存在する場合
dt[dc]=32768; //番兵法的に追加した左の子に最大値を超える値を代入
dc++; //番兵分を加算
dt[dc]=0; //範囲外の右の子を対象にしないための更なる番兵
}
dat=dt;
dat--;
st=gettime(); //開始時刻の取得
//ヒープの構成
for(oya=dc>>1;oya>0;oya--){ //最後の親から最初の親まで繰り返し
osh=oya; //親の添え字を保存
oah=dat[osh]; //親の値を保存
while((ko=osh<<1)<=dc){ //子の添え字がデータ数未満の場合繰り返し
if(dat[ko]<dat[ko+1])ko++; //入れ替え対象の添え字を右の子の添え字に変更
if(oah>=dat[ko])break; //親の保存値の方が子の値より大きい場合はループから抜ける
dat[osh]=dat[ko]; //子の値を親の添え字の位置へ代入
osh=ko; //その時の子の添え字を親の添え字とする
}
dat[osh]=oah; //保存しておいた親の値を代入
}
//ヒープの再構成
while(dc>1){ //添え字の最後から最初まで繰り返し
//右の子まである場合
osh=1; //親の添え字として1を代入
oah=dat[dc]; //最後の添え字の値を親の値として保存
dat[dc]=dat[1]; //最大値を最後の添え字のエリアへ代入
dc--; //添え字のデクリメント（確定した値を除く）
while((ko=osh<<1)<=dc){ //子の添え字がデータ数未満の場合繰り返し
if(dat[ko]<dat[ko+1])ko++; //入れ替え対象の添え字を右の子の添え字に変更
if(oah>=dat[ko])break; //親の保存値の方が子の値より大きい場合はループから抜ける
dat[osh]=dat[ko]; //子の値を親の添え字の位置へ代入
osh=ko; //その時の子の添え字を親の添え字とする
}
dat[osh]=oah; //保存しておいた親の値を代入
//右の子がない場合
osh=1; //親の添え字として1を代入
oah=dat[dc]; //最後の添え字の値を親の値として保存
dat[dc]=dat[1]; //最大値を最後の添え字のエリアへ代入
dc--; //添え字のデクリメント（確定した値を除く）
while((ko=osh<<1)<=dc){ //子の添え字がデータ数未満の場合繰り返し
if(dat[ko]<dat[ko+1])if(ko<dc)ko++; //入れ替え対象の添え字を右の子の添え字に変更
if(oah>=dat[ko])break; //親の保存値の方が子の値より大きい場合はループから抜ける
dat[osh]=dat[ko]; //子の値を親の添え字の位置へ代入
osh=ko; //その時の子の添え字を親の添え字とする
}
dat[osh]=oah; //保存しておいた親の値を代入
}
pt=(gettime()-st)*1000; //処理時間の計算
for(i=0;i<DC;i++){
// printf("%d¥n",dt[i]); //処理結果の表示
if(dt[i]<d)ng++;
d=dt[i];
}
printf("処理時間： %10.4f ミリ秒¥n",pt); //処理時間の表示
if(ng>0)printf("NG発生！:%d",ng); //NG個数の表示
return 0;
}
★ヒープソート５（解説用に最適化したヒープソート）
まぁまぁの速度がでますが、ヒープソート４やヒープソート５には敵いません。
ただし、動きがとてもわかりやすく、解説がしやすいコードにしてありますので、解説するときにご利用ください。
//DreamHopeオリジナル 解説最適化ヒープソート（再帰を使わないヒープソート）
#include <stdio.h>
#include "gettime.h"
#define DC 200000 //データの件数（Windows:258000、Linux:2500000程度が最大値）
int main(void){
int i; //制御変数
int oya; //親の添え字
int osh; //親の添え字保存
int ko; //子の添え字
int wa; //ワークエリア
int dc; //データ数
int dat[DC+1]; //データ格納用配列
double st; //開始時刻（Start Timeの略）
double pt; //処理時間（Processing Timeの略）
srand((unsigned)time(NULL)); //乱数ジェネレータの初期化
for(i=0;i<DC;i++)dat[i]=rand()%32768; //0〜32,767の乱数を生成し配列に格納
st=gettime(); //開始時刻の取得
dc=DC; //データの最大値をdcに代入
//ヒープの構成
for(oya=(int)((dc-2)/2);oya>=0;oya--){ //最後の親から最初の親まで繰り返し
osh=oya; //親の添え字を保存
ko=osh+osh+1; //左の子の添え字を計算
while(ko<dc){ //子の添え字がデータ数未満の場合繰り返し
if(ko<dc-1 && dat[ko]<dat[ko+1])ko++; //右の子が存在し、左の子より右の子が大きい場合、入れ替え対象の添え字を右の子の添え字に変更
if(dat[osh]>=dat[ko])break; //親の保存値の方が子の値以上の場合はループから抜ける
wa=dat[osh]; //ワークエリアへ親の値を代入
dat[osh]=dat[ko]; //子の値を親の添え字の位置へ代入
dat[ko]=wa; //ワークエリアへ退避していた親の値を子の添え字の位置へ代入
osh=ko; //その時の子の添え字を親の添え字とする
ko=osh+osh+1; //この時の左の子の添え字を計算
}
}
//ヒープの再構成
while(dc>0){ //添え字の最後から最初まで繰り返し
dc--; //添え字のデクリメント（これを最初に実行することで上記を成立）
osh=0; //親の添え字として0を代入
wa=dat[dc]; //ワークエリアへ最後の添え字の値を代入
dat[dc]=dat[0]; //最大値を最後の添え字のエリアへ代入
dat[0]=wa; //ワークエリアへ退避していた最後の添え字の値を最初の添え字のエリアへ代入
ko=osh+osh+1; //左の子の添え字を計算
while(ko<dc){ //子の添え字がデータ数未満の場合繰り返し
if(ko<dc-1 && dat[ko]<dat[ko+1])ko++; //右の子が存在し、左の子より右の子が大きい場合、入れ替え対象の添え字を右の子の添え字に変更
if(dat[osh]>=dat[ko])break; //親の保存値の方が子の値以上の場合はループから抜ける
wa=dat[osh]; //ワークエリアへ親の値を代入
dat[osh]=dat[ko]; //子の値を親の添え字の位置へ代入
dat[ko]=wa; //ワークエリアへ退避していた親の値を子の添え字の位置へ代入
osh=ko; //その時の子の添え字を親の添え字とする
ko=osh+osh+1; //この時の左の子の添え字を計算
}
}
pt=(gettime()-st)*1000; //処理時間の計算
// for(i=0;i<DC;i++)printf("%d¥n",dat[i]); //処理結果の表示
printf("処理時間： %10.4f ミリ秒¥n",pt); //処理時間の表示
return 0;
}
ここでの文章、画像、検証結果などは全てDreamHopeに著作権があります。リ ンクに関してはTopLink、DeepLinkともに構いませんが、全部・一部の「学術論文等許諾の不必要な引用」以外の引用に関しては禁止します。
Copyright (C) 2009 DreamHope All Rights Reserved . Access: