Created
August 9, 2017 18:26
-
-
Save cieldeville/7c8910a9825fc5a4897dc2cacfe89979 to your computer and use it in GitHub Desktop.
Implementation of a Binary Heap in Lua
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
| -- heap.lua | |
| -- | |
| -- Provides a binary heap datastructure which may be used | |
| -- by other lua modules and / or scripts (e.g. for pathfinding) | |
| -- | |
| -- Author: BlackyPaw | |
| -- Version: 1.0.0 | |
| -- Last modified: 08/09/2017 | |
| local M = {} | |
| --[[ | |
| --Internals | |
| --]] | |
| local function default_comparator(a, b) | |
| return a < b | |
| end | |
| local function sift_up(heap, i) | |
| local parent = math.floor(i / 2) | |
| if i == 1 or not (heap.sort(heap.elements[i], heap.elements[parent])) then | |
| return | |
| end | |
| heap.elements[i], heap.elements[parent] = heap.elements[parent], heap.elements[i] | |
| sift_up(heap, parent) | |
| end | |
| local function sift_down(heap, i) | |
| local left_child = 2 * i | |
| local right_child = left_child + 1 | |
| if left_child <= heap.n then | |
| local child | |
| if right_child > heap.n or not (heap.sort(heap.elements[right_child], heap.elements[left_child])) then | |
| child = left_child | |
| else | |
| child = right_child | |
| end | |
| if heap.sort(heap.elements[child], heap.elements[i]) then | |
| heap.elements[child], heap.elements[i] = heap.elements[i], heap.elements[child] | |
| sift_down(heap, child) | |
| end | |
| end | |
| end | |
| --[[ | |
| --API | |
| --]] | |
| -- Constructs a new, yet empty binary heap | |
| -- @param comparator The function to be used to compare two elements (optional) | |
| -- @return The newly allocated binary heap | |
| function M.new(comparator) | |
| return { | |
| elements = {}, | |
| sort = comparator or default_comparator, | |
| n = 0 | |
| } | |
| end | |
| -- Checks whether or not the given heap is empty | |
| -- @param heap The heap to check | |
| -- @return Whether or not the given heap is empty | |
| function M.empty(heap) | |
| return (heap.n == 0) | |
| end | |
| -- Returns the number of elements in the given heap (size) | |
| -- @param heap The heap whose size to get | |
| -- @return The number of elements in the heap | |
| function M.size(heap) | |
| return heap.n | |
| end | |
| -- Clears all elements in the given heap | |
| -- @param heap The heap to clear | |
| function M.clear(heap) | |
| heap.elements = {} | |
| heap.n = 0 | |
| end | |
| -- Inserts the element 'e' into the heap 'heap' | |
| -- @param heap The heap the element should be inserted into | |
| -- @param e The element to be inserted | |
| function M.insert(heap, e) | |
| heap.n = heap.n + 1 | |
| heap.elements[heap.n] = e | |
| sift_up(heap, heap.n) | |
| end | |
| -- Peeks at the heap's root element without popping it from the heap and returns it | |
| -- @param heap The heap whose root element to peek | |
| -- @return The peeked root element | |
| function M.peek(heap) | |
| assert(heap.n > 0, "heap is empty") | |
| return heap.elements[1] | |
| end | |
| -- Pops the heap's root element and returns it | |
| -- @param heap The heap whose root element to pop | |
| -- @return The popped root element | |
| function M.pop(heap) | |
| assert(heap.n > 0, "heap is empty") | |
| local result = heap.elements[1] | |
| heap.elements[1], heap.elements[heap.n] = heap.elements[heap.n], nil | |
| heap.n = heap.n - 1 | |
| sift_down(heap, 1) | |
| return result | |
| end | |
| return M |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment