1 ! Implements a heap using an array; top of the heap is the item
2 ! with minimum key value
8 ! Maximum heap size -- maybe make this magically dynamic somehow?
9 integer, parameter :: HEAPSIZE
= 10000
11 ! Type of item to be stored in the heap
13 type (data_node
), pointer :: object
17 type (heap_object
), allocatable
, dimension(:) :: heap
19 ! Index of last item in the heap
20 integer :: end_of_heap
25 ! Initialize the heap; current functionality can be had without
26 ! the need for init function, but we may want more things later
27 subroutine init_heap()
32 allocate(heap(HEAPSIZE
))
34 end subroutine init_heap
37 subroutine heap_destroy()
43 end subroutine heap_destroy
46 subroutine add_to_heap(x
)
51 type (data_node
), pointer :: x
54 integer :: idx
, parent
56 call mprintf((end_of_heap
== HEAPSIZE
),ERROR
, 'add_to_heap(): Maximum heap size exceeded')
58 end_of_heap
= end_of_heap
+ 1
61 heap(idx
)%object
%heap_index
= idx
64 parent
= floor(real(idx
)/2.)
65 if (heap(idx
)%object
%last_used
< heap(parent
)%object
%last_used
) then
66 heap(idx
)%object
=> heap(parent
)%object
67 heap(idx
)%object
%heap_index
= idx
68 heap(parent
)%object
=> x
69 heap(parent
)%object
%heap_index
= parent
76 end subroutine add_to_heap
79 subroutine remove_index(idx
)
84 integer, intent(in
) :: idx
87 integer :: indx
, left
, right
88 type (data_node
), pointer :: temp
90 heap(idx
)%object
=> heap(end_of_heap
)%object
91 heap(idx
)%object
%heap_index
= idx
92 end_of_heap
= end_of_heap
- 1
96 do while (indx
<= end_of_heap
)
99 if (right
<= end_of_heap
) then
100 if (heap(right
)%object
%last_used
< heap(left
)%object
%last_used
) then
101 if (heap(right
)%object
%last_used
< heap(indx
)%object
%last_used
) then
102 temp
=> heap(indx
)%object
103 heap(indx
)%object
=> heap(right
)%object
104 heap(indx
)%object
%heap_index
= indx
105 heap(right
)%object
=> temp
106 heap(right
)%object
%heap_index
= right
109 indx
= end_of_heap
+ 1
112 if (heap(left
)%object
%last_used
< heap(indx
)%object
%last_used
) then
113 temp
=> heap(indx
)%object
114 heap(indx
)%object
=> heap(left
)%object
115 heap(indx
)%object
%heap_index
= indx
116 heap(left
)%object
=> temp
117 heap(left
)%object
%heap_index
= left
120 indx
= end_of_heap
+ 1
123 else if (left
<= end_of_heap
) then
124 if (heap(left
)%object
%last_used
< heap(indx
)%object
%last_used
) then
125 temp
=> heap(indx
)%object
126 heap(indx
)%object
=> heap(left
)%object
127 heap(indx
)%object
%heap_index
= indx
128 heap(left
)%object
=> temp
129 heap(left
)%object
%heap_index
= left
132 indx
= end_of_heap
+ 1
135 indx
= end_of_heap
+ 1
139 end subroutine remove_index
142 subroutine get_min(x
)
147 type (data_node
), pointer :: x
150 integer :: idx
, left
, right
151 type (data_node
), pointer :: temp
153 call mprintf((end_of_heap
<= 0),ERROR
, 'get_min(): No items left in the heap.')
157 heap(1)%object
=> heap(end_of_heap
)%object
158 heap(1)%object
%heap_index
= 1
159 end_of_heap
= end_of_heap
- 1
162 do while (idx
<= end_of_heap
)
165 if (right
<= end_of_heap
) then
166 if (heap(right
)%object
%last_used
< heap(left
)%object
%last_used
) then
167 if (heap(right
)%object
%last_used
< heap(idx
)%object
%last_used
) then
168 temp
=> heap(idx
)%object
169 heap(idx
)%object
=> heap(right
)%object
170 heap(idx
)%object
%heap_index
= idx
171 heap(right
)%object
=> temp
172 heap(right
)%object
%heap_index
= right
175 idx
= end_of_heap
+ 1
178 if (heap(left
)%object
%last_used
< heap(idx
)%object
%last_used
) then
179 temp
=> heap(idx
)%object
180 heap(idx
)%object
=> heap(left
)%object
181 heap(idx
)%object
%heap_index
= idx
182 heap(left
)%object
=> temp
183 heap(left
)%object
%heap_index
= left
186 idx
= end_of_heap
+ 1
189 else if (left
<= end_of_heap
) then
190 if (heap(left
)%object
%last_used
< heap(idx
)%object
%last_used
) then
191 temp
=> heap(idx
)%object
192 heap(idx
)%object
=> heap(left
)%object
193 heap(idx
)%object
%heap_index
= idx
194 heap(left
)%object
=> temp
195 heap(left
)%object
%heap_index
= left
198 idx
= end_of_heap
+ 1
201 idx
= end_of_heap
+ 1
205 end subroutine get_min
207 end module minheap_module