Snippet Minimum Binary Heap

[lep]

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]

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]

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:

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.

 

[Dirac]

Isn't that like bubble sorting?

 

[tooltiperror]

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]

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]

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]

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

 

[Dirac]

like this then?

local thistype node=insert(4)
set node.value=5
call modify(node)

 

[tooltiperror]

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

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]

With the only difference that you didnt use the modify call whatsoever lol.

Anyways already figured it out, thanks.

 

[Nestharus]

local Node node = Heap.insert(5)
call node.modify(6) //change value from 5 to 6

 

[NoobImbaPro]

lol why graveyarded?