Snippet Minimum Binary Heap

[Nestharus]

Good Tutorial on Binary Heaps and Priority Queues

library BH /* v3.0.0.2
*************************************************************************************
*
*   Binary Heap
*
************************************************************************************
*
*   Requires a compare method that compares the first value against a second value
*       < for minimum
*       > for maximum
*
*       private static method compare takes thistype v1, thistype v2 returns boolean
*
*   static readonly thistype root
*       -   The node with the smallest/biggest value
*   readonly thistype node
*       -   Node stored within heap position
*   readonly thistype heap
*       -   Heap position of node
*   static readonly integer size
*       -   Size of binary heap
*   readonly integer value
*       -   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
        readonly static integer size=0
        readonly thistype node              //node
        private static thistype nc=0        //node instance count
        private static thistype array r     //node recycler
        readonly thistype value
        readonly thistype heap
        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

struct Heap extends array
    implement BH
    private static method compare takes integer v1, integer v2 returns boolean
        return v1<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]

This has absolutely no explanation.

 

[Nestharus]

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]

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]

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]

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]

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

Link is in first post.

 

[Darthfett]

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]

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]

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]

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]

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

 

[Nestharus]

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

Because coupling is bad ;D.


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

 

[Nestharus]

Updated

graveyard other

 

[Dirac]

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]

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]

Improved algorithm of delete

Added modify method


Please change thread title to Binary Heap : )

 

[Dirac]

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]

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]

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.