# SnippetMinimum 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 &lt; 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.

Isn't that like bubble sorting?

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.

like this then?
JASS:
``````local thistype node=insert(4)
set node.value=5
call modify(node)``````

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

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

lol why graveyarded?

General chit-chat
Help Users
• No one is chatting at the moment.
• The Helper:
News portal has been retired. Main page of site goes to Headline News forum now
• 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:
Easily done
+1
• 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:
Need to try something
• Ghan:
Hopefully this won't cause problems.
• Ghan:
Hmm
• 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:
See how we like that.
• The Helper:
I do not see a way to go past the 1st page of posts on the forum though
• 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:
Yeah I'm not sure what the deal is with the pagination.
• Ghan:
It SHOULD be there so I think it might just be an artifact of having an older style.
• 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:
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:
RpNation makes more use of it right now as an example: https://www.rpnation.com/news/
• The Helper:
• The Helper:
What do you think Tom?
• tom_mai78101:
I will have to get used to this.
• tom_mai78101:
The latest news feed looks good
• 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:
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/

### Members online

No members online now.