Snippet Minimum Binary Heap

lep

Active Member
Reaction score
8
This is a must. I'm trying to create a method that retrieves the closest unit of a group to a point, and doesn't work for multiple groups because the binary heap can't be erased.

But you don't need a heap to do that. Atleast not if you only want the one nearest unit.
 

Dirac

22710180
Reaction score
147
You're not presenting me the answer, and why wouldn't you need a heap? Heaps return the smallest/highest value of a list very fast
 

lep

Active Member
Reaction score
8
You're not presenting me the answer, and why wouldn't you need a heap? Heaps return the smallest/highest value of a list very fast

Using a heap for n insertions you get a time-complexity of O(n*ln n). Everyone agrees? (Don't know if i use the right terminology, correct me if im wrong.)
Now lets consider this:
JASS:
globals
    unit minUnit
    real minDist

    real tmpX
    real tmpY
endglobals

function foldl takes nothing returns nothing
    local unit u = GetEnumUnit()
    local real currentDist
    if minUnit == null
        set minUnit = u
        set minDist = distance(minUnit, tmpX, tmpY)
    else
        set currentDist = distance(u, tmpX, tmpY)
        if currentDist < minDist
            set minDist = currentDist
            set minUnit = u
        endif
    endif
    set u=null
endfunction

function findNearest takes location loc, group units returns unit // null | found unit
    set minUnit=null
    set minDist=0
    set tmpX=GetLocationX(loc)
    set tmpY=GetLocationY(loc)
    call ForGroup(g, function foldl)
    return minUnit
endfunction

This has a time-complexitiy of O(n) where n is the number of units in the group.

Or in other words, if i only want the smallest/highest value of a list, which is not sorted, i simply walk through the list and save the smallest/highest value. No need for complex operations like building a heap.

e: Ofc, time-complexity is not always an sign for actual faster execution, but this is so way more straightforward. And if Jass were an actual high-level language it could be even more shorter, more readable and more generic.
 

tooltiperror

Super Moderator
Reaction score
231
Or, you can use a Fan of Knives dummy ability w/ a dummy unit, and use event responses to get this in a hacky way without as much Jass.

;)
 

Nestharus

o-o
Reaction score
84
Dirac, you're using binary heap all wrong. I didn't add clear because it just doesn't seem useful for what binary heaps are useful for. If you find yourself needing clear, then you aren't using binary heaps correctly.


For getting units within range of another unit, or finding the closest unit to another unit, you do not use binary heaps. For finding closest unit, you'd want to use a Kd-Tree of x and y and a nearest neighbor search.

A Kd-Tree is part of the field of computational geometry. Here is a whole set of lectures on computational geometry, which will drastically help you with your problems ^)^.

Computational Geometry
 

Dirac

22710180
Reaction score
147
How exactly should i use the modify method? shouldn't it take 2 integers? heap to modify and new value?

What value it currently modifies? (how does it work?)
 

Nestharus

o-o
Reaction score
84
[ljass]static method insert takes thistype v returns thistype[/ljass]

see how that returns a node. You can then proceed to modify the value of that node and it'll resort the binary heap or w/e for you.
 

tooltiperror

Super Moderator
Reaction score
231
>local thistype node=insert(4)
Please don't do this. "insert" is assumed to be a function, because you imply the 'thistype'. But it's really a static method. You need some verbosity in your code.

Anyways, it would be like this.

JASS:
library ExampleHeap initializer onInit requires BH

private struct DataHeap extends array
    // This struct is a heap, because it extends array and implements
    // his module.
    implement BH
endstruct

private function onInit takes nothing returns nothing
    call DataHeap.insert(3)
    call DataHeap.insert(2)
    call DataHeap.insert(-4)
    call DataHeap.insert(1)
    call DataHeap.insert(-2)

    call BJDebugMsg(I2S(DataHeap.size))  // displays 5

    // Loop while the heap is not empty (an empty heap has a size of 0)
    loop
        exitwhen DataHeap.size == 0

        call BJDebugMsg(I2S(DataHeap.root))       // Display the first node
        call DataHeap.delete(DataHeap.root.node)  // Remove the first node

        // Remember, the list is sorted least to greatest
        // Output: -4; -2; 1; 2; 3
    endloop
endfunction

endlibrary
 

Dirac

22710180
Reaction score
147
With the only difference that you didnt use the modify call whatsoever lol.

Anyways already figured it out, thanks.
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top