# SnippetMinimum Binary Heap

#### Nestharus

##### o-o
Good Tutorial on Binary Heaps and Priority Queues

JASS:
``````
library BH /* v3.0.0.2
*************************************************************************************
*
*   Binary Heap
*
************************************************************************************
*
*   Requires a compare method that compares the first value against a second value
*       &lt; for minimum
*       &gt; for maximum
*
*       private static method compare takes thistype v1, thistype v2 returns boolean
*
*       -   The node with the smallest/biggest value
*       -   Node stored within heap position
*       -   Heap position of node
*       -   Size of binary heap
*       -   Sorted value (the value of the node)
*
*   method modify takes integer sortValue returns nothing
*       -   Modifies the value of the node
*
*   static method insert takes integer sortValue returns thistype
*       -   Inserts a new node into the heap and returns it
*   static method delete takes thistype node returns nothing
*       -   Deletes node from heap
*
************************************************************************************/
module BH
private static thistype nc=0        //node instance count
private static thistype array r     //node recycler
static method operator root takes nothing returns thistype
return thistype(1).node
endmethod
static method allocate takes thistype v returns thistype
local thistype i
if (0==r[0]) then
set i=nc+1
set nc=i
else
set i=r[0]
set r[0]=r<i>
endif
set i.value=v
return i
endmethod
method deallocate takes nothing returns nothing
set r[this]=r[0]
set r[0]=this
endmethod
method modify takes integer v returns nothing
local thistype i=heap
local thistype m
local thistype o
set value=v

//bubble moved node down
loop
set m=i*2       //left
set o=m+1       //right
exitwhen (0==m.node or compare(value,m.node.value)) and (0==o.node or compare(value,o.node.value))
if (0==o.node.value or (0!=m.node and compare(m.node.value,o.node.value))) then
set i.node=m.node
set i.node.heap=i
set i=m
else
set i.node=o.node
set i.node.heap=i
set i=o
endif
endloop
set i.node=this
set heap=i
endmethod
static method insert takes thistype v returns thistype
local thistype i=size+1         //heap node
local thistype p=i/2            //parent
local thistype m
set size=i

//allocate node
if (0==r[0]) then
set m=nc+1
set nc=m
else
set m=r[0]
set r[0]=r[m]
endif
set m.value=v

loop
exitwhen 0==p or compare(p.node.value,v)
set i.node=p.node
set i.node.heap=i
set i=p
set p=p/2
endloop
set i.node=m
set m.heap=i

return m
endmethod
static method delete takes thistype i returns nothing
local thistype this=thistype(size).node
local thistype m
local thistype o
debug if (0&lt;size) then
//deallocate deleted node
set m=i.node
set r[m]=r[0]
set r[0]=m
set thistype(size).node=0
set size=size-1

//bubble moved node down
loop
set m=i*2       //left
set o=m+1       //right
exitwhen (0==m.node or compare(value,m.node.value)) and (0==o.node or compare(value,o.node.value))

if (0==o.node.value or (0!=m.node and compare(m.node.value,o.node.value))) then
set i.node=m.node
set i.node.heap=i
set i=m
else
set i.node=o.node
set i.node.heap=i
set i=o
endif
endloop
set i.node=this
set heap=i
debug endif
endmethod
endmodule
endlibrary
</i>``````

Demo
JASS:
``````
struct Heap extends array
implement BH
private static method compare takes integer v1, integer v2 returns boolean
return v1&lt;v2
endmethod
private static method onInit takes nothing returns nothing
call insert(5)
call insert(9)
call insert(3)
call insert(2)
call insert(-1)
call insert(16)
loop
exitwhen 0==size
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,I2S(root.value))
call delete(1) //or call delete(root.heap), but delete 1 is faster
endloop
//-1,2,3,5,9,16
endmethod
endstruct``````

#### tooltiperror

##### Super Moderator
This has absolutely no explanation.

#### Nestharus

##### o-o
I shouldn't need to explain data structures that you can just as easily google.

However, I would be willing to put a link up to wikipedia's page or a tutorial.

That is the most you are going to get.

#### tooltiperror

##### Super Moderator
Every resource needs a blerb describing what it's useful for, when to be used in comparison to something else, maybe how it is implemented, et cetera.

#### Nestharus

##### o-o
Posted a lecture

That should cover it all =)

Binary Heaps are mostly used for priority queues and memory allocation. Priority queues are used for things like timers and path finding among other things =).

I've never seen a priority stack used, but I use it in my special path finding.

I've also never seen a priority list, but a priority list allows one to remove any element at any point from the heap, which can be extremely useful for timers ^)^.

#### Romek

##### Super Moderator
Staff member
I don't think a 42 minute youtube lecture qualifies as a 'brief description of your resource'. And it still doesn't show how to use this resource specifically.

> I've never seen a priority stack used, but I use it in my special path finding.
Maybe you would've been better off just inlining it into your code, rather than posting a separate resource which nobody will ever use.

#### Nestharus

##### o-o
Romek, you know I don't couple >: P.

Anyways, the Path finding one already has an minimum inlined binary heap + priority stack, heh. It doesn't need a couple of things in this.

Let's see if I can find a brief tutorial on heaps.

edit
Found a pretty in-depth tutorial that explains what priority queues are used for, what they are, and what binary heaps are used for and what they are. The basic description is all on the first page. The next page shows what a binary heap looks like complete with pics ^)^.

It also has a java app to demo insert so you can see exactly what it does ^)^.

#### Darthfett

##### Aerospace/Cybersecurity Software Engineer
Make sure you include a description on HOW to implement it. It's a module, so it's not going to be as simple as people are used to.

Heaps support only one of each value
Make sure you also mention that only your resource has this limitation, as this is not a flaw with the data structure.

#### Nestharus

##### o-o
Make sure you also mention that only your resource has this limitation, as this is not a flaw with the data structure.
I removed that line and updated docs on priority queue, stack, and list ^)^.

It should be fairly obvious how to implement by reading the API =), but I added a demo

#### Darthfett

##### Aerospace/Cybersecurity Software Engineer
It should be fairly obvious how to implement by reading the API =), but I added a demo
Thanks.

I removed that line and updated docs on priority queue, stack, and list ^)^.
If it still has this flaw, it should still be mentioned.

#### Nestharus

##### o-o
It actually never had that flaw, hence why I removed it =P

It's a very standard binary heap =), well excluding the heap pointer and the ability to delete any node in the heap =P.

#### Sim

Staff member
Why not combine your 5 snippets into a system or something.

#### Nestharus

##### o-o
Why not combine your 5 snippets into a system or something.

Anyways, I might add a cycle operation to this, which will reinsert the head. It'd be more efficient than a delete + create as the insert operation wouldn't need to be done. The thing would just bubble down, rather than bubbling down, then bubbling last up, then bubbling the node back up.

I did that in a timer system I am working on =). So far it's at 40 fps vs 60 fps. The next update will hopefully make it faster than timers and only run on a single timer ^)^.

Updated

graveyard other

#### Dirac

##### 22710180
Once again you found a more difficult way to make things more efficient.

I find this very interesting, i'm reading the lecture posted

EDIT: why when i type this
[ljass]call BJDebugMsg(R2S(thistype(1).node.value))[/ljass]
[ljass]call BJDebugMsg(R2S(thistype(2).node.value))[/ljass]
[ljass]call BJDebugMsg(R2S(thistype(3).node.value))[/ljass]
it returns wrong values? except for the first one. Isn't the heap sorted every time you insert a node? why not?
you should add [ljass]static method sort[/ljass] then.

#### Nestharus

##### o-o
The heap isn't meant to be sorted?

The values it returns are correct... a binary heap is partially sorted. The only value that is a given is the first one.

So no, the heap isn't sorted every time you insert a node : P. If you want something that's sorted every time you insert a node, you'd want some sort of tree, like a red black tree or avl tree.

I do have a mostly coded red black tree lib, which specializes in insertions and deletions, but eh ; ). All that I have left to code in it is a portion of the delete method and it's set to go =P.

#### Nestharus

##### o-o
Improved algorithm of delete

#### Dirac

##### 22710180
I was trying to use this and i gotta say, the API is extremely confusing and / or missing important things.

What's the allocate method for? serves no aparent use so far
What's the deallocate method for? same thing
There's no clear method, so it's impossible to delete the whole heap without sorting it entirely?
Does this support multiple heaps? how? where?

#### Nestharus

##### o-o
Because of the nature of binary heaps, you can't do multi instanced binary heaps in vjass.

Allocate/Deallocate forcefully allocates/deallocates nodes. It's for when you code stuff from scratch, which I did do in one system.

There is no way to clear a binary heap at this time, no ; P, but it's easy to write one up.

#### Dirac

##### 22710180
There is no way to clear a binary heap at this time, no ; P, but it's easy to write one up.
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.

General chit-chat
Help Users
• No one is chatting at the moment.
• jonas:
where did you go?
• The Helper:
Jefferson TX on a Paranormal Investigation of a haunted bed and breakfast - I got some friends that are paranormal investigators and they have an RV and do YouTubes
+1
• The Helper:
It was a lot of fun. The RV was bad ass
• jonas:
That sounds like fun!
+1
• The Helper:
it was a blast!
• The Helper:
I am going to post the Youtube of the investigation in the forums when it is ready
+1
• jonas:
cool!
• vypur85:
Sounds cool TH.
• tom_mai78101:
I was on a Legend of Zelda marathon...
• tom_mai78101:
Am still doing it now
+1
• jonas:
which one(s) are you playing?
• jonas:
I played a little bit of the switch title two weeks ago and found it quite boring
• The Helper:
just got back from San Antonio this weekend had the best Buffalo Chicken Cheesesteak sandwhich in Universal City, TX - place was called Yous Guys freaking awesome! Hope everyone had a fantastic weekend!
+1
• The Helper:
Happy Tuesday!
• The Helper:
We have been getting crazy numbers reported by the forum of people online the bots are going crazy on us I think it is AI training bots going at it at least that is what it looks like to me.
• The Helper:
Most legit traffic is tracked on multiple Analytics and we have Cloud Flare setup to block a ton of stuff but still there is large amount of bots that seem to escape detection and show up in the user list of the forum. I have been watching this bullshit for a year and still cannot figure it out it is drving me crazy lol.
+1
• Ghan:
Beep boop
+1
• The Helper:
hears robot sounds while 250 bots are on the forum lol
• The Helper:
Happy Saturday!
+1
• The Helper:
and then it was Thursday...
+2
• tom_mai78101:
And then Monday
+1
• The Helper:
I got the day off today!
+1
• tom_mai78101:
How...? (T-T)
• The Helper:
I took the day off. I work for myself so I can do that.
+1
• Varine:

### Members online

No members online now.