• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

[Snippet] Priority Stack

Level 31
Joined
Jul 10, 2007
Messages
6,306
Good Tutorial on Binary Heaps and Priority Queues

JASS:
library PS /* v1.0.0.2
*************************************************************************************
*
*   Priority Stack
*
*       i.e.
*           struct Test extends array
*               implement PS
*
*               //code
*
*           endstruct
*
************************************************************************************
*
*   */uses/*
*
*       */ Table /*       hiveworkshop.com/forums/jass-functions-413/snippet-new-table-188084/
*       */ BH /*          hiveworkshop.com/forums/submissions-414/snippet-minimum-binary-heap-199353/
*
************************************************************************************
*
*   static readonly thistype floor
*       -   The node with the floor value (max or min)
*
*   static method add takes integer value returns thistype
*       -   Adds a new value and returns the node that has it.
*   static method remove takes nothing returns nothing
*       -   Removes the floor value node
*
************************************************************************************/
    module PS
        implement BH
        
        private static thistype array n     //next
        private static Table t              //table
        private static method onInit takes nothing returns nothing
            set t=Table.create()
        endmethod
        static method operator floor takes nothing returns thistype
            return n[thistype(1).node]
        endmethod
        static method add takes integer v returns thistype
            local thistype i=t[v]
            local thistype m=allocate(v)
            set n[m]=0
            if (0==i) then
                set i=insert(v)
                set t[v]=i
                set n[i]=0
            endif
            set n[m]=n[i]
            set n[i]=m
            return m
        endmethod
        static method remove takes nothing returns nothing
            local thistype m
            local thistype k
            if (0<size) then
                set m=thistype(1).node
                set k=n[m]
                set n[m]=n[k]
                call k.deallocate()
                if 0==n[m] then
                    call t.remove(m.value)
                    call delete(1)
                endif
            endif
        endmethod
    endmodule
endlibrary
 
Last edited:

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
When would someone use this over Priority Queue? Or vice-versa. More explaination helps.
Since both libraries made by Nes have much in common, I'd say it highly depends on users preferences.

In both cases it's implementation of INSERT, EXTRACT-ROOT and ROOT (the highest element in MAX-Heap or the lowest in MIN-Heap) - and there isn't much of a difference ;P

Anyways, I'm wondering why "add" method returns data object, instead of nothing. Demo code would be great. Normaly, the task of insertion is to add new element, increasing the size of heap and using "fixUp" method to repair the heap.
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
I have never ever seen a PriorityStack used for anything, lol. Relatively useless and I doubt anyone has ever used this.

Might as well graveyard it. It's one of those things that I put up just because I thought, hey, I'm going to write a PriorityStack for the hell of it, rofl rofl, look at me go ;o.

Ah, those were the days.
 
Top