Last active
December 15, 2023 21:43
-
-
Save meseta/e6fa3d3747b4228f9aeb805307f8717f to your computer and use it in GitHub Desktop.
GML MaxHeap implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** A max-heap implementation (i.e. priority queue). value-priority pairs can be inserted into the heap, which wil | |
* efficiently maintain sort order, and the maximum priorty value can be queried at any time | |
* @author Meseta https://meseta.dev | |
*/ | |
function MaxHeap() constructor { | |
/* @ignore */ self.__values = []; // Heap-ordered storage. array of value/priority pairs, the zerth index is maintained to be highest priority | |
/* @ignore */ self.__length = 0; | |
/** Returns how many elements are in the heap | |
* @return {Real} | |
*/ | |
static get_length = function() { | |
return self.__length; | |
}; | |
/** Insert a value into the heap | |
* @param {Any} _value The value to insert | |
* @param {Real} _priority The priority of the value to insert, can be any number | |
*/ | |
static insert = function(_value, _priority) { | |
array_push(self.__values, [_value, _priority]); | |
self.__length += 1 | |
self.__shift_up(self.__length-1); | |
}; | |
/** Removes the highest value/priority pair from the heap, and returns it as an array | |
* in the format [value, priority]; undefined will be returned if there's no values available | |
* @return {Array*} | |
*/ | |
static pop_max = function() { | |
if (self.__length == 0) { | |
return undefined; | |
} | |
var _result = self.__values[0]; | |
self.__remove_max(); | |
return _result | |
}; | |
/** Removes the highest value/priority pair from the heap, and returns the value | |
* @return {Any*} | |
*/ | |
static pop_max_value = function() { | |
if (self.__length == 0) { | |
return undefined; | |
} | |
var _result = self.__values[0][0]; | |
self.__remove_max(); | |
return _result; | |
}; | |
/** Removes the highest value/priority pair from the heap, and returns the priority | |
* @return {Real*} | |
*/ | |
static pop_max_priority = function() { | |
if (self.__length == 0) { | |
return undefined; | |
} | |
var _result = self.__values[0][1]; | |
self.__remove_max(); | |
return _result; | |
}; | |
/** Fetch the highest value/priority pair from the heap without removing it, and returns it as an array | |
* in the format [value, priority]; undefined will be returned if there's no values available | |
* @return {Array*} | |
*/ | |
static peek_max = function() { | |
return self.__length ? self.__values[0] : undefined; | |
}; | |
/** Fetch the value of highest priority value from the heap without removing it | |
* @return {Any*} | |
*/ | |
static peek_max_value = function() { | |
return self.__length ? self.__values[0][0] : undefined; | |
}; | |
/** Fetch the highest priority value from the heap without removing it | |
* @return {Real*} | |
*/ | |
static peek_max_priority = function() { | |
return self.__length ? self.__values[0][1] : undefined; | |
}; | |
/** Clears the heap, resetting it to blank */ | |
static clear = function() { | |
self.__values = []; | |
self.__length = 0; | |
}; | |
/** Internal function for managing the heap. Removes the highest priority value from the heap | |
* @ignore | |
*/ | |
static __remove_max = function() { | |
self.__length -= 1; | |
self.__values[0] = self.__values[self.__length]; | |
array_resize(self.__values, self.__length); | |
self.__shift_down(0); | |
}; | |
/** Internal function for managing the heap. Shift all the priority values down | |
* @ignore | |
*/ | |
static __shift_down = function(_idx) { | |
var _max_idx = _idx; | |
var _left = self.__left_child(_idx); | |
if (_left < self.__length and self.__values[_left][1] > self.__values[_max_idx][1]) { | |
_max_idx = _left; | |
} | |
var _right = self.__right_child(_idx); | |
if (_right < self.__length and self.__values[_right][1] > self.__values[_max_idx][1]) { | |
_max_idx = _right; | |
} | |
if (_idx != _max_idx) { | |
self.__swap(_idx, _max_idx); | |
self.__shift_down(_max_idx); | |
} | |
}; | |
/** Internal function for managing the heap. Shift all the values up | |
* @ignore | |
*/ | |
static __shift_up = function(_idx) { | |
while(_idx > 0) { | |
var _parent_idx = self.__parent(_idx); | |
if (self.__values[_parent_idx][1] >= self.__values[_idx][1]) { | |
break; | |
} | |
self.__swap(_parent_idx, _idx); | |
_idx = _parent_idx; | |
} | |
}; | |
/** Internal function for managing the heap. Get the parent index in the heap index system | |
* @param {Real} _idx the index to get the parent of | |
* @return {Real} | |
* @pure | |
* @ignore | |
*/ | |
static __parent = function(_idx) { | |
return (_idx - 1) div 2; | |
}; | |
/** Internal function for managing the heap. Get the left child index in the heap index system | |
* @param {Real} _idx the index to get the left child of | |
* @return {Real} | |
* @pure | |
* @ignore | |
*/ | |
static __left_child = function(_idx) { | |
return (2*_idx) + 1; | |
}; | |
/** Internal function for managing the heap. Get the right child index in the heap index system | |
* @param {Real} _idx the index to get the right child of | |
* @return {Real} | |
* @pure | |
* @ignore | |
*/ | |
static __right_child = function(_idx) { | |
return (2*_idx) + 2; | |
}; | |
/** Internal function for managing the heap. Swaps two indexes | |
* @param {Real} _left_idx one of the indices to swap | |
* @param {Real} _right_idx the other index to swap | |
* @ignore | |
*/ | |
static __swap = function(_left_idx, _right_idx) { | |
var _temp = self.__values[_left_idx]; | |
self.__values[_left_idx] = self.__values[_right_idx]; | |
self.__values[_right_idx] = _temp; | |
}; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment