※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

  1. use strict;
  2. use warnings;
  3.  
  4. my $LIST_SIZE ||= 20;
  5. my @heap;
  6.  
  7. for(my $i = 0; $i < $LIST_SIZE; $i++){
  8. $heap[$i] = int($i);
  9. }
  10.  
  11. #ランダムに並び替える
  12. for (my $i = @heap; --$i; ) {
  13. my $j = int rand ($i + 1);
  14. next if $i == $j;
  15. @heap[$i, $j] = @heap[$j, $i];
  16. }
  17.  
  18. # 1個目はダミー
  19. my @g_heap = (-1);
  20.  
  21. print_array(\@heap); # 実行前
  22. &heapsort(\@heap);
  23. print_array(\@heap); # 実行後
  24.  
  25. sub heapsort{
  26. my $array = shift;
  27. &insertheap($array);
  28. for(my $i = 0; $i < scalar(@$array); $i++){
  29. $array->[$i] = &get_root;
  30. }
  31. }
  32.  
  33. sub insertheap{
  34. my $array = shift;
  35. for(my $i = 0; $i < scalar(@$array); $i++){
  36. push @g_heap, $array->[$i];
  37. upheap($#g_heap);
  38. }
  39. }
  40.  
  41. sub upheap{
  42. my $index = shift;
  43. my $tmp = $g_heap[$index];
  44. while( ($index > 1) && ($g_heap[int($index / 2)] > $tmp)){
  45. $g_heap[$index] = $g_heap[int($index / 2)];
  46. $index = int($index / 2);
  47. }
  48. $g_heap[$index] = $tmp;
  49. }
  50.  
  51. sub get_root{
  52. my $tmp;
  53. if( scalar(@g_heap) < 1){
  54. print "ヒープが空です";
  55. }
  56. $tmp = $g_heap[1];
  57. $g_heap[1] = $g_heap[$#g_heap];
  58.  
  59. pop @g_heap;
  60.  
  61. &downheap;
  62. return $tmp;
  63. }
  64.  
  65. sub downheap{
  66.  
  67. if(scalar(@g_heap) < 2){
  68. }
  69.  
  70. my $tmp = $g_heap[1];
  71.  
  72. my $i = 1;
  73.  
  74. while($i <= int($#g_heap / 2)){
  75. my $j = $i * 2;
  76.  
  77. if( ($j + 1 <= $#g_heap) && ($g_heap[$j] > $g_heap[$j + 1]) ){
  78. $j++;
  79. }
  80.  
  81. if($tmp <= $g_heap[$j]){
  82. last;
  83. }
  84.  
  85. $g_heap[$i] = $g_heap[$j];
  86. $i = $j;
  87. }
  88. $g_heap[$i] = $tmp;
  89. }
  90.  
  91. sub print_array{
  92. my $ref_array = shift;
  93. for my $i(@$ref_array){
  94. print "$i ";
  95. }
  96. print "\n";
  97. }
  98.  




| 新しいページ | 編集 | 差分 | 編集履歴 | ページ名変更 | アップロード | 検索 | ページ一覧 | タグ | RSS | ご利用ガイド | 管理者に問合せ |
@wiki - 無料レンタルウィキサービス | プライバシーポリシー