Ooops
January 15, 2021, 06:29:31 PM

Author Topic: [bb] Binary Heaps by pexe [ 1+ years ago ]  (Read 605 times)

BlitzBot

• Jr. Member
• Posts: 1
[bb] Binary Heaps by pexe [ 1+ years ago ]
« on: June 29, 2017, 12:28:42 AM »
Title : Binary Heaps
Author : pexe
Posted : 1+ years ago

Description : binaryheaps.bb V1.0
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Matheus Cansian

This LIB provide tools to create Binary Heaps ordered lists. It
can handle more than one simultaneous list and ascending and
descending order.

HOW-TO: Create a list with New(), use one of the sorting
constants to select with each sorting order your list will
operate. Then use the functions Add(), Remove() and Modify(), to
manipulate the data within the list.
If you need a debug tool, you can use Draw() to show all your
list elements.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Example:

BinID% = BinaryHeap_New%(BinaryHeap_SORT_BIGGEST) ;Create a new list

;Get the biggest value
print BinaryHeap_Remove%(BinID) ;Output: Second

Code :
Code: BlitzBasic
1. ;;;;                    binaryheaps.bb V1.0
2. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
3. ;;;;                      Matheus Cansian
4. ;;;;
5. ;;;; This LIB provide tools to create Binary Heaps ordered lists. It
6. ;;;; can handle more than one simultaneous list and ascending and
7. ;;;; descending order.
8. ;;;;
9. ;;;; HOW-TO: Create a list with New(), use one of the sorting
10. ;;;; constants to select with each sorting order your list will
11. ;;;; operate. Then use the functions Add(), Remove() and Modify(), to
12. ;;;; manipulate the data within the list.
13. ;;;; If you need a debug tool, you can use Draw() to show all your
14. ;;;; list elements.
15.
16.
17. ;; LIB CONFIGURATIONS ;;
18. Const BinaryHeap_MaxElements% = 1000   ;Max of elements each list can store
19. Const BinaryHeap_MaxSimultaneous% = 5  ;Max simultaneous list you can have
20.
21. ;Note: Memory storage is calculated by multiplying MaxElements with MaxSimoultaneous.
22. ;      eg: MaxElements = 1000 and MaxSimultaneous = 5
23. ;          1000 * 5 = 5000 bytes or approx. 5 KB
24.
25.
26. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; LIB ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
27. ;;;;;;;;;;; Probably there's nothing you need to change down there! ;;;;;;;;;;;;
28.
29. ;; LIB CONSTANTS ;;
30. Const BinaryHeap_Version\$ = "1.0"
31. Const BinaryHeap_SORT_SMALLEST = 1
32. Const BinaryHeap_SORT_BIGGEST  = 2
33.
34. ;; LIB ARRAYS ;;
35. Dim BinaryHeap_Sort%(BinaryHeap_MaxSimultaneous%) ;What kind of sorting method?
36. Dim BinaryHeap_Elements%(BinaryHeap_MaxSimultaneous%) ;Count the number of elements
37. Dim BinaryHeap_Value%(BinaryHeap_MaxSimultaneous%, BinaryHeap_MaxElements%)
38. Dim BinaryHeap_Data% (BinaryHeap_MaxSimultaneous%, BinaryHeap_MaxElements%)
39.
40. ;;; <summary>Create a list ordered list</summary>
41. ;;; <param name="SortMethod">How the list will be sorted? Use the constants above</param>
42. ;;; <remarks></remarks>
43. ;;; <returns></returns>
44. ;;; <subsystem></subsystem>
45. ;;; <example></example>
46. Function BinaryHeap_New%(SortMethod%)
47.         For Cont% = 1 To BinaryHeap_MaxSimultaneous%
48.                 If BinaryHeap_Sort%(Cont%) = 0 Then
49.                         BinaryHeap_Sort%(Cont%) = SortMethod%
50.                         Return Cont%
51.                 Else
52.                         DebugLog Cont
53.                 EndIf
54.         Next
55.         Return 0
56. End Function
57.
58. ;;; <summary>Delete a binary heap thread</summary>
60. ;;; <remarks></remarks>
61. ;;; <returns>1 if the thread was deleted, 0 if the thread dont exists</returns>
62. ;;; <subsystem></subsystem>
63. ;;; <example></example>
65.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
66.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0
67.
68.         ;Clear Sort and Elements variables
69.         BinaryHeap_Sort%(BinaryHeapThread%) = 0
70.         BinaryHeap_Elements%(BinaryHeapThread%) = 0
71.
72.         ;Clear Value and Data variables
73.         For Cont% = 1 To BinaryHeap_MaxElements%
74.                 BinaryHeap_Value%(BinaryHeapThread%, Cont%) = 0
75.                 BinaryHeap_Data% (BinaryHeapThread%, Cont%) = 0
76.         Next
77.
78.         Return 1
79. End Function
80.
83.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
84.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
85.
86.         ;Check if max elements reached
87.         If BinaryHeap_Elements%(BinaryHeapThread%) >= BinaryHeap_MaxElements% Then Return 0 ;Max elements reached
88.
89.         ;Add Elements counter
91.
92.         ;Get the last element position
93.         Local MyElement% = BinaryHeap_Elements%(BinaryHeapThread%)
94.
95.         ;Add element to the end of the list
96.         BinaryHeap_Value%(BinaryHeapThread%, MyElement)  = Value%
97.         BinaryHeap_Data%(BinaryHeapThread%, MyElement)   = HeapData%
98.
99.         ;Get sorting method
100.         Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%)
101.
102.         Local MyValue%, ParentValue%, ParentElement%
103.         Repeat
104.                 ;Get parent position
105.                 ParentElement% = Floor(MyElement%/2)
106.                 If ParentElement% <= 0 Then Exit
107.
108.                 ;Get elements values
109.                 MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement)
110.                 ParentValue% = BinaryHeap_Value%(BinaryHeapThread%, ParentElement)
111.
112.                 ;Compare data
113.                 If (MyValue% >= ParentValue% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= ParentValue% And Sort_Method% = BinaryHeap_SORT_BIGGEST) Then
114.                         ;Leave it alone
115.                         Exit
116.                 Else
117.                         ;Swap elements
118.                         BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, ParentElement)
119.
120.                          ;Get new element position
121.                          MyElement = ParentElement
122.                 EndIf
123.         Forever
124.         Return 1
125. End Function
126.
127. ;;; <summary>Get the first heap element</summary>
128. ;;; <param name="BinaryHeapThread"></param>
129. ;;; <remarks></remarks>
130. ;;; <returns></returns>
131. ;;; <subsystem></subsystem>
132. ;;; <example></example>
135.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
136.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
137.
138.         ;Check if the are elements
139.         If BinaryHeap_Elements%(BinaryHeapThread%) <= 0 Then Return 0 ;No elements
140.
141.         ;Decrease Elements counter
143.
144.         ;Save first element data
145.         Local FirstData% = BinaryHeap_Data% (BinaryHeapThread%, 1)
146.
147.         ;Delete first element
148.         BinaryHeap_Value% (BinaryHeapThread%, 1) = 0
149.         BinaryHeap_Data%  (BinaryHeapThread%, 1) = 0
150.
151.         ;Swap last element with first
153.
154.         ;Get sorting method
155.         Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%)
156.
157.         Local MyValue%, Child1Value%, Child2Value%, Child1Active%, Child2Active%, Child1Element%, Child2Element%, MyElement% = 1
158.         Repeat
159.                 ;Get element child
160.                 Child1Element% = Floor(MyElement%*2)
161.                 Child2Element% = Floor(MyElement%*2)+1
162.
163.                 ;Get elements value
164.                 MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement%)
165.                 If (Child1Element%<=BinaryHeap_MaxElements%) Then Child1Value% = BinaryHeap_Value%(BinaryHeapThread%, Child1Element%):Else:Child1Value% = 0
166.                 If (Child2Element%<=BinaryHeap_MaxElements%) Then Child2Value% = BinaryHeap_Value%(BinaryHeapThread%, Child2Element%):Else:Child2Value% = 0
167.
168.                 ;Get elements status
169.                 If (Child1Element%<=BinaryHeap_MaxElements%) Then Child1Active% = (BinaryHeap_Data%(BinaryHeapThread%, Child1Element%)<>0):Else:Child1Active% = 0
170.                 If (Child2Element%<=BinaryHeap_MaxElements%) Then Child2Active% = (BinaryHeap_Data%(BinaryHeapThread%, Child2Element%)<>0):Else:Child2Active% = 0
171.
172.                 ;Compare data
173.                 If (Child1Active% And ((MyValue% >= Child1Value% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= Child1Value% And Sort_Method% = BinaryHeap_SORT_BIGGEST))) Or (Child2Active% And ((MyValue% >= Child2Value% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= Child2Value% And Sort_Method% = BinaryHeap_SORT_BIGGEST))) Then
174.                         If Child1Active% And ((Child1Value% <= Child2Value% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (Child1Value% >= Child2Value% And Sort_Method% = BinaryHeap_SORT_BIGGEST))
175.                                 ;Swap with child 1
176.                                 BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, Child1Element)
177.                                 ;Get new element position
178.                                 MyElement = Child1Element
179.                         Else
180.                                 ;Swap with child 2
181.                                 BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, Child2Element)
182.                                 ;Get new element position
183.                                 MyElement = Child2Element
184.                         EndIf
185.                 Else
186.                         ;Leave it alone
187.                         Exit
188.                 EndIf
189.         Forever
190.
191.         Return FirstData%
192. End Function
193.
194. ;;; <summary>Change an element value</summary>
195. ;;; <param name="BinaryHeapThread"></param>
196. ;;; <param name="Value"></param>
197. ;;; <param name="HeapData"></param>
198. ;;; <param name="NewValue"></param>
199. ;;; <remarks></remarks>
200. ;;; <returns>1 if succeed, 0 if fail</returns>
201. ;;; <subsystem></subsystem>
202. ;;; <example></example>
203. Function BinaryHeap_Modify%(BinaryHeapThread%, Value%, HeapData%, NewValue%)
205.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
206.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
207.
208.         ;Store number of elements
209.         TotalElements% = BinaryHeap_Elements%(BinaryHeapThread%)
210.
211.         ;Search for the element
212.         For Cont% = 1 To TotalElements%
213.                 If BinaryHeap_Value%(BinaryHeapThread%, Cont) = Value% And BinaryHeap_Data%(BinaryHeapThread%, Cont) = HeapData% Then
214.                         MyElement% = Cont%
215.                         Exit
216.                 EndIf
217.         Next
218.
219.         ;Change element data
220.         BinaryHeap_Value%(BinaryHeapThread%, MyElement%) = NewValue%
221.
222.         ;Get sorting method
223.         Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%)
224.
225.         Local MyValue%, ParentValue%, ParentElement%
226.         Repeat
227.                 ;Get parent position
228.                 ParentElement% = Floor(MyElement%/2)
229.                 If ParentElement% <= 0 Then Exit
230.
231.                 ;Get elements values
232.                 MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement)
233.                 ParentValue% = BinaryHeap_Value%(BinaryHeapThread%, ParentElement)
234.
235.                 ;Compare data
236.                 If (MyValue% >= ParentValue% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= ParentValue% And Sort_Method% = BinaryHeap_SORT_BIGGEST) Then
237.                         ;Leave it alone
238.                         Exit
239.                 Else
240.                         ;Swap elements
241.                         BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, ParentElement)
242.
243.                          ;Get new element position
244.                          MyElement = ParentElement
245.                 EndIf
246.         Forever
247.         Return 1
248. End Function
249.
250. ;;; <summary>Draw the BinaryHeaps structure in the screen</summary>
251. ;;; <param name="BinaryHeapThread"></param>
252. ;;; <param name="SkipKey">Keycode to exit, or 0 to exit automatically</param>
253. ;;; <param name="Levels">Number of levels to draw, or 0 to draw all</param>
254. ;;; <remarks></remarks>
255. ;;; <returns>Level drawn or 0 for failure</returns>
256. ;;; <subsystem></subsystem>
257. ;;; <example></example>
258. Function BinaryHeap_Draw%(BinaryHeapThread%, SkipKey%=0, Levels%=0)
260.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
261.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
262.
263.         ;Get graphics size
264.         Local Width% = GraphicsWidth()
265.         Local Height% = GraphicsHeight()
266.
267.         ;Clear screen
268.         SetBuffer BackBuffer():ClsColor 200,200,200
269.
270.         ;Get total os elements
271.         Local MaxElements% = BinaryHeap_Elements%(BinaryHeapThread%)
272.
273.         ;Get number of levels
274.         Local Elements% = 0, MaxLevels%
275.         Repeat
276.                 Elements% = Elements% * 2
277.                 Elements% = Elements% + 1
278.                 MaxLevels% = MaxLevels% + 1
279.                 If Elements% >= MaxElements% Then Exit
280.         Forever
281.         If Levels% =  0 Then Levels% = MaxLevels%
282.         If MaxElements% <=  1 Then Levels% = 2
283.
284.         Local FirstPosition%, LevelSpacing%, LevelElements%, LevelSpacingSteps%, LastLevelSize%
285.         Local OffsetX%, OffsetY%, Value%, HeapActive%
286.         Repeat
287.                 ;Get input keys
288.                 If KeyDown(200) Then OffsetY = OffsetY + 10
289.                 If KeyDown(208) Then OffsetY = OffsetY - 10
290.                 If KeyDown(205) Then OffsetX = OffsetX - 10
291.                 If KeyDown(203) Then OffsetX = OffsetX + 10
292.                 If KeyHit(201) And Levels% < MaxLevels% Then Levels% = Levels% + 1
293.                 If KeyHit(209) And Levels% > 1 Then Levels% = Levels% - 1
294.
295.                 Cls
296.
298.                 Color 0,0,0
299.                 Text OffsetX+Width%/2, OffsetY+5,"Exploring BinaryHeap: "+BinaryHeapThread%+" | TotalElements: "+MaxElements%,1,0
300.                 Text OffsetX+Width%/2, OffsetY+25,"Use PAGEUP/DOWN to change the number of levels and keyboard arrows to move",1,0
301.
302.
303.                 ;Draw Elements
304.                 LastLevelSize% = ((2^Levels%)/2)*StringWidth(" 100 ")*2
305.                 For Level% = 1 To Levels%
306.                         FirstPosition% = 2^(Level%-1)
307.                         LevelSpacing% = LastLevelSize% / 2^Level%
308.                         LevelElements% = (2^Level%)/2
309.                         LevelSpacingSteps% = -(LevelElements%-1)
310.
311.                         For Pos% = 0 To LevelElements%-1
312.                                 ;Check if maximum reached
313.                                 If FirstPosition%+Pos% > BinaryHeap_MaxElements% Then Exit
314.
315.                                 ;Get element value and data%
316.                                 Value% = BinaryHeap_Value%(BinaryHeapThread%, FirstPosition%+Pos%)
317.                                 HeapActive% = (BinaryHeap_Data%(BinaryHeapThread%, FirstPosition%+Pos%)<>0)
318.
319.                                 ;Draw child lines
320.                                 If Level% < Levels%
321.                                         Color 180,180,180
322.                                         ;These lines are a total mess!!
323.                                         Line OffsetX+(Width%/2)+LevelSpacing%*(LevelSpacingSteps%+2*Pos%), OffsetY+Level%*20+40, OffsetX+(Width%/2)+(LastLevelSize% / 2^(Level%+1))*((-((2^(Level%+1))/2-1))+2*Pos%*2), OffsetY+(Level%+1)*20+40
324.                                         Line OffsetX+(Width%/2)+LevelSpacing%*(LevelSpacingSteps%+2*Pos%), OffsetY+Level%*20+40, OffsetX+(Width%/2)+(LastLevelSize% / 2^(Level%+1))*((-((2^(Level%+1))/2-1))+2*((Pos%*2)+1)), OffsetY+(Level%+1)*20+40
325.                                 EndIf
326.
327.                                 ;Draw element value
328.                                 If HeapActive% <> 0 Then Color 0,0,0:Else:Color 230,100,100
329.                                 Text OffsetX+(Width%/2)+LevelSpacing%*(LevelSpacingSteps%+2*Pos%), OffsetY+Level%*20+40,Value%,1,1
330.                         Next
331.                 Next
332.                 Flip
333.         Until (KeyHit(SkipKey)) Or SkipKey%=0
334.
335.         Return Levels%
336. End Function
337.
338. ;;; <summary>Swap two elements</summary>
340. ;;; <param name="Position1">Position of the first element</param>
341. ;;; <param name="Position2">Position of the second element</param>
342. ;;; <remarks></remarks>
343. ;;; <returns>1 for successful 0 for failure</returns>
344. ;;; <subsystem></subsystem>
345. ;;; <example></example>
346. Function BinaryHeap_Private_Swap(BinaryHeapThread%, Position1%, Position2%)
348.         If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0
349.         If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists
350.
351.         ;Store temp variables
352.         Local TempValue%  = BinaryHeap_Value% (BinaryHeapThread%, Position1%)
353.         Local TempData%   = BinaryHeap_Data%  (BinaryHeapThread%, Position1%)
354.
355.         ;Change first
356.         BinaryHeap_Value% (BinaryHeapThread%, Position1%) = BinaryHeap_Value% (BinaryHeapThread%, Position2%)
357.         BinaryHeap_Data%  (BinaryHeapThread%, Position1%) = BinaryHeap_Data%  (BinaryHeapThread%, Position2%)
358.
359.         BinaryHeap_Value%(BinaryHeapThread%, Position2%) = TempValue%
360.         BinaryHeap_Data% (BinaryHeapThread%, Position2%) = TempData%
361.
362.         Return 1
363. End Function