Code archives/Algorithms/Binary Heaps
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
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 BinaryHeap_Add%(BinID,32,"First") ;Add a value BinaryHeap_Add%(BinID,68,"Second") ;Add a value BinaryHeap_Add%(BinID,15,"Third") ;Add a value ;Get the biggest value print BinaryHeap_Remove%(BinID) ;Output: Second | |||||
;;;; 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. ;; LIB CONFIGURATIONS ;; Const BinaryHeap_MaxElements% = 1000 ;Max of elements each list can store Const BinaryHeap_MaxSimultaneous% = 5 ;Max simultaneous list you can have ;Note: Memory storage is calculated by multiplying MaxElements with MaxSimoultaneous. ; eg: MaxElements = 1000 and MaxSimultaneous = 5 ; 1000 * 5 = 5000 bytes or approx. 5 KB ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; LIB ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;; Probably there's nothing you need to change down there! ;;;;;;;;;;;; ;; LIB CONSTANTS ;; Const BinaryHeap_Version$ = "1.0" Const BinaryHeap_SORT_SMALLEST = 1 Const BinaryHeap_SORT_BIGGEST = 2 ;; LIB ARRAYS ;; Dim BinaryHeap_Sort%(BinaryHeap_MaxSimultaneous%) ;What kind of sorting method? Dim BinaryHeap_Elements%(BinaryHeap_MaxSimultaneous%) ;Count the number of elements Dim BinaryHeap_Value%(BinaryHeap_MaxSimultaneous%, BinaryHeap_MaxElements%) Dim BinaryHeap_Data% (BinaryHeap_MaxSimultaneous%, BinaryHeap_MaxElements%) ;;; <summary>Create a list ordered list</summary> ;;; <param name="SortMethod">How the list will be sorted? Use the constants above</param> ;;; <remarks></remarks> ;;; <returns></returns> ;;; <subsystem></subsystem> ;;; <example></example> Function BinaryHeap_New%(SortMethod%) For Cont% = 1 To BinaryHeap_MaxSimultaneous% If BinaryHeap_Sort%(Cont%) = 0 Then BinaryHeap_Sort%(Cont%) = SortMethod% Return Cont% Else DebugLog Cont EndIf Next Return 0 End Function ;;; <summary>Delete a binary heap thread</summary> ;;; <param name="BinaryHeapThread">BinaryHeap Thread ID</param> ;;; <remarks></remarks> ;;; <returns>1 if the thread was deleted, 0 if the thread dont exists</returns> ;;; <subsystem></subsystem> ;;; <example></example> Function BinaryHeap_Delete%(BinaryHeapThread%) If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0 If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Clear Sort and Elements variables BinaryHeap_Sort%(BinaryHeapThread%) = 0 BinaryHeap_Elements%(BinaryHeapThread%) = 0 ;Clear Value and Data variables For Cont% = 1 To BinaryHeap_MaxElements% BinaryHeap_Value%(BinaryHeapThread%, Cont%) = 0 BinaryHeap_Data% (BinaryHeapThread%, Cont%) = 0 Next Return 1 End Function Function BinaryHeap_Add%(BinaryHeapThread%, Value%, HeapData%) ;Check HeapThread If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0 If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists ;Check if max elements reached If BinaryHeap_Elements%(BinaryHeapThread%) >= BinaryHeap_MaxElements% Then Return 0 ;Max elements reached ;Add Elements counter BinaryHeap_Elements%(BinaryHeapThread%) = BinaryHeap_Elements%(BinaryHeapThread%) + 1 ;Get the last element position Local MyElement% = BinaryHeap_Elements%(BinaryHeapThread%) ;Add element to the end of the list BinaryHeap_Value%(BinaryHeapThread%, MyElement) = Value% BinaryHeap_Data%(BinaryHeapThread%, MyElement) = HeapData% ;Get sorting method Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%) Local MyValue%, ParentValue%, ParentElement% Repeat ;Get parent position ParentElement% = Floor(MyElement%/2) If ParentElement% <= 0 Then Exit ;Get elements values MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement) ParentValue% = BinaryHeap_Value%(BinaryHeapThread%, ParentElement) ;Compare data If (MyValue% >= ParentValue% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= ParentValue% And Sort_Method% = BinaryHeap_SORT_BIGGEST) Then ;Leave it alone Exit Else ;Swap elements BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, ParentElement) ;Get new element position MyElement = ParentElement EndIf Forever Return 1 End Function ;;; <summary>Get the first heap element</summary> ;;; <param name="BinaryHeapThread"></param> ;;; <remarks></remarks> ;;; <returns></returns> ;;; <subsystem></subsystem> ;;; <example></example> Function BinaryHeap_Remove%(BinaryHeapThread%) ;Check HeapThread If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0 If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists ;Check if the are elements If BinaryHeap_Elements%(BinaryHeapThread%) <= 0 Then Return 0 ;No elements ;Decrease Elements counter BinaryHeap_Elements%(BinaryHeapThread%) = BinaryHeap_Elements%(BinaryHeapThread%) - 1 ;Save first element data Local FirstData% = BinaryHeap_Data% (BinaryHeapThread%, 1) ;Delete first element BinaryHeap_Value% (BinaryHeapThread%, 1) = 0 BinaryHeap_Data% (BinaryHeapThread%, 1) = 0 ;Swap last element with first BinaryHeap_Private_Swap(BinaryHeapThread%, 1, BinaryHeap_Elements%(BinaryHeapThread%)+1) ;Get sorting method Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%) Local MyValue%, Child1Value%, Child2Value%, Child1Active%, Child2Active%, Child1Element%, Child2Element%, MyElement% = 1 Repeat ;Get element child Child1Element% = Floor(MyElement%*2) Child2Element% = Floor(MyElement%*2)+1 ;Get elements value MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement%) If (Child1Element%<=BinaryHeap_MaxElements%) Then Child1Value% = BinaryHeap_Value%(BinaryHeapThread%, Child1Element%):Else:Child1Value% = 0 If (Child2Element%<=BinaryHeap_MaxElements%) Then Child2Value% = BinaryHeap_Value%(BinaryHeapThread%, Child2Element%):Else:Child2Value% = 0 ;Get elements status If (Child1Element%<=BinaryHeap_MaxElements%) Then Child1Active% = (BinaryHeap_Data%(BinaryHeapThread%, Child1Element%)<>0):Else:Child1Active% = 0 If (Child2Element%<=BinaryHeap_MaxElements%) Then Child2Active% = (BinaryHeap_Data%(BinaryHeapThread%, Child2Element%)<>0):Else:Child2Active% = 0 ;Compare data 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 If Child1Active% And ((Child1Value% <= Child2Value% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (Child1Value% >= Child2Value% And Sort_Method% = BinaryHeap_SORT_BIGGEST)) ;Swap with child 1 BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, Child1Element) ;Get new element position MyElement = Child1Element Else ;Swap with child 2 BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, Child2Element) ;Get new element position MyElement = Child2Element EndIf Else ;Leave it alone Exit EndIf Forever Return FirstData% End Function ;;; <summary>Change an element value</summary> ;;; <param name="BinaryHeapThread"></param> ;;; <param name="Value"></param> ;;; <param name="HeapData"></param> ;;; <param name="NewValue"></param> ;;; <remarks></remarks> ;;; <returns>1 if succeed, 0 if fail</returns> ;;; <subsystem></subsystem> ;;; <example></example> Function BinaryHeap_Modify%(BinaryHeapThread%, Value%, HeapData%, NewValue%) ;Check HeapThread If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0 If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists ;Store number of elements TotalElements% = BinaryHeap_Elements%(BinaryHeapThread%) ;Search for the element For Cont% = 1 To TotalElements% If BinaryHeap_Value%(BinaryHeapThread%, Cont) = Value% And BinaryHeap_Data%(BinaryHeapThread%, Cont) = HeapData% Then MyElement% = Cont% Exit EndIf Next ;Change element data BinaryHeap_Value%(BinaryHeapThread%, MyElement%) = NewValue% ;Get sorting method Local Sort_Method% = BinaryHeap_Sort%(BinaryHeapThread%) Local MyValue%, ParentValue%, ParentElement% Repeat ;Get parent position ParentElement% = Floor(MyElement%/2) If ParentElement% <= 0 Then Exit ;Get elements values MyValue% = BinaryHeap_Value%(BinaryHeapThread%, MyElement) ParentValue% = BinaryHeap_Value%(BinaryHeapThread%, ParentElement) ;Compare data If (MyValue% >= ParentValue% And Sort_Method% = BinaryHeap_SORT_SMALLEST) Or (MyValue% <= ParentValue% And Sort_Method% = BinaryHeap_SORT_BIGGEST) Then ;Leave it alone Exit Else ;Swap elements BinaryHeap_Private_Swap(BinaryHeapThread%, MyElement, ParentElement) ;Get new element position MyElement = ParentElement EndIf Forever Return 1 End Function ;;; <summary>Draw the BinaryHeaps structure in the screen</summary> ;;; <param name="BinaryHeapThread"></param> ;;; <param name="SkipKey">Keycode to exit, or 0 to exit automatically</param> ;;; <param name="Levels">Number of levels to draw, or 0 to draw all</param> ;;; <remarks></remarks> ;;; <returns>Level drawn or 0 for failure</returns> ;;; <subsystem></subsystem> ;;; <example></example> Function BinaryHeap_Draw%(BinaryHeapThread%, SkipKey%=0, Levels%=0) ;Check HeapThread If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0 If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists ;Get graphics size Local Width% = GraphicsWidth() Local Height% = GraphicsHeight() ;Clear screen SetBuffer BackBuffer():ClsColor 200,200,200 ;Get total os elements Local MaxElements% = BinaryHeap_Elements%(BinaryHeapThread%) ;Get number of levels Local Elements% = 0, MaxLevels% Repeat Elements% = Elements% * 2 Elements% = Elements% + 1 MaxLevels% = MaxLevels% + 1 If Elements% >= MaxElements% Then Exit Forever If Levels% = 0 Then Levels% = MaxLevels% If MaxElements% <= 1 Then Levels% = 2 Local FirstPosition%, LevelSpacing%, LevelElements%, LevelSpacingSteps%, LastLevelSize% Local OffsetX%, OffsetY%, Value%, HeapActive% Repeat ;Get input keys If KeyDown(200) Then OffsetY = OffsetY + 10 If KeyDown(208) Then OffsetY = OffsetY - 10 If KeyDown(205) Then OffsetX = OffsetX - 10 If KeyDown(203) Then OffsetX = OffsetX + 10 If KeyHit(201) And Levels% < MaxLevels% Then Levels% = Levels% + 1 If KeyHit(209) And Levels% > 1 Then Levels% = Levels% - 1 Cls ;Draw header Color 0,0,0 Text OffsetX+Width%/2, OffsetY+5,"Exploring BinaryHeap: "+BinaryHeapThread%+" | TotalElements: "+MaxElements%,1,0 Text OffsetX+Width%/2, OffsetY+25,"Use PAGEUP/DOWN to change the number of levels and keyboard arrows to move",1,0 ;Draw Elements LastLevelSize% = ((2^Levels%)/2)*StringWidth(" 100 ")*2 For Level% = 1 To Levels% FirstPosition% = 2^(Level%-1) LevelSpacing% = LastLevelSize% / 2^Level% LevelElements% = (2^Level%)/2 LevelSpacingSteps% = -(LevelElements%-1) For Pos% = 0 To LevelElements%-1 ;Check if maximum reached If FirstPosition%+Pos% > BinaryHeap_MaxElements% Then Exit ;Get element value and data% Value% = BinaryHeap_Value%(BinaryHeapThread%, FirstPosition%+Pos%) HeapActive% = (BinaryHeap_Data%(BinaryHeapThread%, FirstPosition%+Pos%)<>0) ;Draw child lines If Level% < Levels% Color 180,180,180 ;These lines are a total mess!! 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 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 EndIf ;Draw element value If HeapActive% <> 0 Then Color 0,0,0:Else:Color 230,100,100 Text OffsetX+(Width%/2)+LevelSpacing%*(LevelSpacingSteps%+2*Pos%), OffsetY+Level%*20+40,Value%,1,1 Next Next Flip Until (KeyHit(SkipKey)) Or SkipKey%=0 Return Levels% End Function ;;; <summary>Swap two elements</summary> ;;; <param name="BinaryHeapThread">BinaryHeap thread ID</param> ;;; <param name="Position1">Position of the first element</param> ;;; <param name="Position2">Position of the second element</param> ;;; <remarks></remarks> ;;; <returns>1 for successful 0 for failure</returns> ;;; <subsystem></subsystem> ;;; <example></example> Function BinaryHeap_Private_Swap(BinaryHeapThread%, Position1%, Position2%) ;Check HeapThread If (BinaryHeapThread% <= 0) Or (BinaryHeapThread% > BinaryHeap_MaxSimultaneous%) Then Return 0 If BinaryHeap_Sort%(BinaryHeapThread%) = 0 Then Return 0 ;Thread dont exists ;Store temp variables Local TempValue% = BinaryHeap_Value% (BinaryHeapThread%, Position1%) Local TempData% = BinaryHeap_Data% (BinaryHeapThread%, Position1%) ;Change first BinaryHeap_Value% (BinaryHeapThread%, Position1%) = BinaryHeap_Value% (BinaryHeapThread%, Position2%) BinaryHeap_Data% (BinaryHeapThread%, Position1%) = BinaryHeap_Data% (BinaryHeapThread%, Position2%) BinaryHeap_Value%(BinaryHeapThread%, Position2%) = TempValue% BinaryHeap_Data% (BinaryHeapThread%, Position2%) = TempData% Return 1 End Function |
Comments
None.
Code Archives Forum