Snippet Minimum Binary Heap

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.
 
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
 
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.
 
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.

;)
 
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
 
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?)
 
[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.
 
>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
 
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 The Helper:
    News portal has been retired. Main page of site goes to Headline News forum now
  • The Helper The Helper:
    I am working on getting access to the old news portal under a different URL for those that would rather use that for news before we get a different news view.
  • Ghan Ghan:
    Easily done
    +1
  • The Helper The Helper:
    https://www.thehelper.net/pages/news/ is a link to the old news portal - i will integrate it into the interface somewhere when i figure it out
  • Ghan Ghan:
    Need to try something
  • Ghan Ghan:
    Hopefully this won't cause problems.
  • Ghan Ghan:
    Hmm
  • Ghan Ghan:
    I have converted the Headline News forum to an Article type forum. It will now show the top 20 threads with more detail of each thread.
  • Ghan Ghan:
    See how we like that.
  • The Helper The Helper:
    I do not see a way to go past the 1st page of posts on the forum though
  • The Helper The Helper:
    It is OK though for the main page to open up on the forum in the view it was before. As long as the portal has its own URL so it can be viewed that way I do want to try it as a regular forum view for a while
  • Ghan Ghan:
    Yeah I'm not sure what the deal is with the pagination.
  • Ghan Ghan:
    It SHOULD be there so I think it might just be an artifact of having an older style.
  • Ghan Ghan:
    I switched it to a "Standard" article forum. This will show the thread list like normal, but the threads themselves will have the first post set up above the rest of the "comments"
  • The Helper The Helper:
    I don't really get that article forum but I think it is because I have never really seen it used on a multi post thread
  • Ghan Ghan:
    RpNation makes more use of it right now as an example: https://www.rpnation.com/news/
  • The Helper The Helper:
  • The Helper The Helper:
    What do you think Tom?
  • tom_mai78101 tom_mai78101:
    I will have to get used to this.
  • tom_mai78101 tom_mai78101:
    The latest news feed looks good
  • The Helper The Helper:
    I would like to see it again like Ghan had it the first time with pagination though - without the pagination that view will not work but with pagination it just might...
  • The Helper The Helper:
    This drink recipe I have had more than a few times back in the day! Mind Eraser https://www.thehelper.net/threads/cocktail-mind-eraser.194720/

      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