Fortran 95 source code to generate a heap by downward method.

heap_downward.f95

!****************************************************
! ヒープ作成（下方移動）
!
!   date          name            version
!   2018.12.06    mk-mode.com     1.00 新規作成
!
! Copyright(C) 2018 mk-mode.com All Rights Reserved.
!****************************************************
!
module const
  implicit none
  ! SP: 単精度(4), DP: 倍精度(8)
  integer,     parameter :: SP = kind(1.0)
  integer(SP), parameter :: DP = selected_real_kind(2 * precision(1.0_SP))
  integer(SP), parameter :: N = 100  ! データ個数
end module const

module heap
  use const, only : SP, DP
  implicit none
  private
  public :: gen_heap

contains
  ! ヒープ生成
  !
  ! :param(in)    integer(4) num: データ個数
  ! :param(inout) integer(4)   h: ヒープ配列
  subroutine gen_heap(num, h)
    implicit none
    integer(SP), intent(in)    :: num
    integer(SP), intent(inout) :: h(0:num)
    integer(SP) :: i, s, p, w

    do i = num / 2, 1, -1
      p = i         ! 親要素の位置
      s = 2 * p     ! 左の子要素の位置
      do while (s <= num)
        ! 左右子要素の小さい方
        if (s < num .and. h(s + 1) < h(s)) s = s + 1
        if (h(p) <= h(s)) exit
        w    = h(p)
        h(p) = h(s)
        h(s) = w
        p = s       ! 親要素の位置
        s = 2 * p   ! 左の子要素の位置
      end do
    end do
  end subroutine gen_heap
end module heap

program heap_downward
  use const
  use heap
  implicit none
  integer(SP) :: h(0:N)  ! ヒープ配列
  integer(SP) :: seed_size, clock, i
  real(DP)    :: r
  integer(SP), allocatable :: seed(:)

  ! 乱数の種の設定
  ! (元の配列を毎回異なる内容にするため)
  call system_clock(clock)
  call random_seed(size=seed_size)
  allocate(seed(seed_size))
  seed = clock
  call random_seed(put=seed)
  deallocate(seed)

  ! 元の配列生成（(0, N] の値の配列）
  do i = 1, N
    call random_number(r)
    h(i) = int(r * N) + 1
  end do
  print '(A)', "#### Base"
  print '(10(X, I4))', h(1:)

  ! ヒープ配列生成
  call gen_heap(N, h)
  print '(A)', "#### Heap"
  print '(10(X, I4))', h(1:)
end program heap_downward