• Hey! Guest! The 40th (!!!) GMC Jam will take place between February 25th, 12:00 UTC to March 1st 12:00 UTC. Why not join in this very special anniversary jam! Click here to find out more!
  • Hello [name]! Thanks for joining the GMC. Before making any posts in the Tech Support forum, can we suggest you read the forum rules? These are simple guidelines that we ask you to follow so that you can get the best help possible for your issue.

 Suggestion: Ds_heap

GMWolf

aka fel666
Heaps are an essential data structure that is unfortunately missing from GML. (Though yes, priority queues can be used in many cases).

What I suggest is the inclusion of a new data structure called ds_heap, with the following functions:
(The heap would use an array representation internally)

Ds_heap_create(comp_script)
Creates a new Ds_heap. Comp_script is the script used to compare elements.

Ds_heap_sift_up(heap, index)
Sifts an element up the heap.

Ds_heap_sift_down(heap, index)
Sifts an element down the heap.

Ds_heap_find_max(heap)
Returns max (A[0]) element.

Ds_heap_find_min(heap)
Returns min (A[n]) element.

Ds_heap_delete_max(heap)
Deletes and return max

Ds_heap_delete_min(heap)
Deletes and returns min

Ds_heap_insert(heap, value)
Inserts value into heap.

Ds_list_heapify(list, comp_script)
Heapifies the list and returns a new heap index, with comp_script as the comparative script.


The functions would allow the user to define the comparative script. This would allow objects, arrays etc to be passed, and be compared as the user wants.
(Currently working on some path finding. This would be super useful).

P.s. currently, ds_list_find_value, ds_map_find_value, etc can only return reals and strings. So if you stored an array, you musr use accessors.
This is a problem with priority queues; they don't have accessors.
 

Mike

nobody important
GMC Elder
I'm not actually sure what you're determining is a heap. Normally a heap is a block of memory that you allocate other things from, but you don't need this in GML.

Also, you can store arrays(or grids) in lists etc, so I'm not sure where you're going with this, or why you need it.
 

YellowAfterlife

ᴏɴʟɪɴᴇ ᴍᴜʟᴛɪᴘʟᴀʏᴇʀ
Forum Staff
Moderator
P.s. currently, ds_list_find_value, ds_map_find_value, etc can only return reals and strings. So if you stored an array, you musr use accessors.
Who told you that, they return any stored values (including arrays, pointers, and "undefined") perfectly fine. In fact, if you look at "VMASM" view in the debugger...
upload_2017-1-10_13-4-47.png
Accessor compiles to the very same function call.

There was at one point a bug where ds_list_find_index wouldn't search for arrays, but it is resolved in current versions.

Also, your suggestion looks an awful lot like priority queues. Have you taken a look at priority queues?
 

GMWolf

aka fel666
I'm not actually sure what you're determining is a heap. Normally a heap is a block of memory that you allocate other things from, but you don't need this in GML.

Also, you can store arrays(or grids) in lists etc, so I'm not sure where you're going with this, or why you need it.
I'm not actually sure what you're determining is a heap. Normally a heap is a block of memory that you allocate other things from, but you don't need this in GML.

Also, you can store arrays(or grids) in lists etc, so I'm not sure where you're going with this, or why you need it.
Im talking about the heap data structure: https://en.wikipedia.org/wiki/Heap_(data_structure)

Its basically a really, really efficient way of doing priority queues ( O(log N) insert and delete operations, O(1) find, and O(n) heapify)

Its generally a really useful data structure to have around. Yes, because its best represented as an array / list, i could add my own scripts. (in fact, im doing that already). But it would be nice for everyone to have by default.

Its very useful when dealing with graphs. I needed it for path finding. Buts its also great for minimal spanning trees, etc.
Its also a more full fleged alternative to priority queues.

@YellowAfterlife Really? When i last tested it it didnt work :(
i wanst using the degugger, just show_message statements.
 
Last edited:

Mike

nobody important
GMC Elder
Okay, a tree.... A tree is pretty easy to do in GML as it is...

Code:
root[0] = data
root[1] = left[]
root[2] = right[]

right[0]=data
right[1]=undefined
right[2]=right_end[]

left[0] = data
left[1] = undefined
left[2] = undefined

right end[0]=data
right_end[1] = undefined
right_end[2] = undefined
and so on..... So each "node" holds 3 values (or as many as you'd like) but 2 of them are the left/right tree branches.
 
Last edited:

GMWolf

aka fel666
Okay, a tree.... A tree is pretty easy to do in GML as it is...

Code:
root[0] = data
root[1] = left[]
root[2] = right[]

right[0]=data
right[1]=undefined
right[2]=right_end[]

left[0] = data
left[1] = undefined
left[2] = undefined

right end[0]=data
right_end[1] = undefined
right_end[2] = undefined
and so on..... So each "node" holds 3 values (or as many as you'd like) bu 2 of them are the left/right tree branches.
That's pretty inefficient. Since heaps are essentially complete, its much better to use array representation.

I have already implemented my own heaps using lists. It works fine. I can use it.

But it would be great to see it part of gm.
 

Mike

nobody important
GMC Elder
Why is this inefficient? arrays are faster than lists, they are managed - so delete one node, all the memory the the rest is removed as well. It's a win-win. It should be faster to allocate as it's a built in type....

Heaps would basically be doing this behind the scenes, I see no reason to add in a data type that is so easy to make, and that's going to be just as fast, if not quicker.
 

GMWolf

aka fel666
Why is this inefficient?
You can represent an entire heap in a single array. So a heap with 10 nodes just needs a list with a length of 10.

You can the access any node in O(1) time. This is because the tree is complete. So you can find the index of children easily. (I*2 and I*2+1)

I assume heapify, sift up and sift down would run much better if written in C code rather than GML.
Also without all the GML accessing overhead.

But I guess we don't need it. More of a quality of life feature.
 

Mike

nobody important
GMC Elder
Finding a child would still involve traversing the tree, the index is irrelevant. Once you get the child index, you'll still need to look it up. Storing as arrays, finding the child, you already have the variable you need. Yes its in one memory block, but you also have the issue of allocation, and freeing of nodes requiring a separate list of "free" slots you need to allocate from.

If allocation isn't a worry - because its a one shot thing, or rarely done, then arrays still win out as traversing time is the same, and you don't have the final lookup to get the actual data - you have it already.

Still unconvinced. To me, its something else that is SO simple to implement in GML, there's no point doing native version of it. Would it speed up? Perhaps - not convinced as you'd still have to manually search each node for the thing you want, which is a call - just like an accessor.

unconvinced.....
 

GMWolf

aka fel666
Finding a child would still involve traversing the tree, the index is irrelevant. Once you get the child index, you'll still need to look it up. Storing as arrays, finding the child, you already have the variable you need. Yes its in one memory block, but you also have the issue of allocation, and freeing of nodes requiring a separate list of "free" slots you need to allocate from.
Not with array representation of heaps.
This is done on a level per level basis. You don't need to Traverse a heap.


But regardless, yes, its pretty easily added in GML. And so fair enough, it doesn't need a native implementation.
 

Mike

nobody important
GMC Elder
okay... so ignoring the request to add it. I'm curious as to why you need a tree if you never traverse it? if its all stored as indexes, why do you need a tree?
 

GMWolf

aka fel666
okay... so ignoring the request to add it. I'm curious as to why you need a tree if you never traverse it? if its all stored as indexes, why do you need a tree?
I recommende you check out the wiki page... Its pretty good.

But its essentially a priority queue. Every time you add/remove something, it gets percolated up or sifted down to sit on the right place.
These two operations only requires to access children's and parents.
Because heaps are essentially complete trees, its pretty trivial to find the children and parents with an array representation. (Multiply and divide the index by 2).

BTW, I haven't tested, but it doesn't seem the current priority queues use heaps internally. It probably should for better performance :)

Las I needed it was because priority queues didn't return arrays. (So I built my own based on heaps)
But I think that things like prim's algorithm benefit from heaps greatly.
 
Last edited:
T

TimothyAllen

Guest
Heaps are an essential data structure that is unfortunately missing from GML. (Though yes, priority queues can be used in many cases).

What I suggest is the inclusion of a new data structure called ds_heap, with the following functions:
(The heap would use an array representation internally)

Ds_heap_create(comp_script)
Creates a new Ds_heap. Comp_script is the script used to compare elements.

Ds_heap_sift_up(heap, index)
Sifts an element up the heap.

Ds_heap_sift_down(heap, index)
Sifts an element down the heap.

Ds_heap_find_max(heap)
Returns max (A[0]) element.

Ds_heap_find_min(heap)
Returns min (A[n]) element.


Ds_heap_delete_max(heap)
Deletes and return max

Ds_heap_delete_min(heap)
Deletes and returns min

Ds_heap_insert(heap, value)
Inserts value into heap.

Ds_list_heapify(list, comp_script)
Heapifies the list and returns a new heap index, with comp_script as the comparative script.


The functions would allow the user to define the comparative script. This would allow objects, arrays etc to be passed, and be compared as the user wants.
(Currently working on some path finding. This would be super useful).

P.s. currently, ds_list_find_value, ds_map_find_value, etc can only return reals and strings. So if you stored an array, you musr use accessors.
This is a problem with priority queues; they don't have accessors.
I highlighted something in your post that confuses me. I don't believe you can have a find min and find max in that manner on the same heap. At that point, the heap is nothing more than a sorted array no? If you have a min heap, finding tha max value is not effiecent and vise versa. (talking from little experience with heaps here).

Mike was using arrays before they named them "arrays", so don't teach him ;)
I know your trying to suck up, but it sounds like youre calling him old... very old.
 

GMWolf

aka fel666
I highlighted something in your post that confuses me. I don't believe you can have a find min and find max in that manner on the same heap. At that point, the heap is nothing more than a sorted array no? If you have a min heap, finding tha max value is not effiecent and vise versa. (talking from little experience with heaps here).
There is still a pretty efficient (ish) way:
Loop through the second 1/2 of the array. pick out the min of that.

But yes, it wont be O(1) to find min in a max heap.
Same with finding max in a min heap.
 
Top