Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Fortran 95 source code to generate a heap by downward method.
!****************************************************
! ヒープ作成(下方移動)
!
! 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.