mirror of
https://github.com/arendst/Tasmota.git
synced 2026-06-11 12:55:33 -04:00
55 lines
1.5 KiB
Plaintext
55 lines
1.5 KiB
Plaintext
# https://en.wikipedia.org/wiki/Binary_heap
|
|
# This allows to choose the M first elements of an N-sized array
|
|
# with respect to a comparison predicate cmp that defines a total order.
|
|
# This avoids the overhead of sorting the entire array and then picking
|
|
# the first elements. This is related to a priority queue.
|
|
# We also define a binary heap based sort() of an entire array.
|
|
|
|
var binary_heap = module("binary_heap")
|
|
|
|
binary_heap._heapify = def(array, cmp, i)
|
|
var m = i, child, e, am, ac
|
|
while true
|
|
child = 2 * i + 1
|
|
if child >= array.size() return end
|
|
ac = array[child]
|
|
am = array[m]
|
|
if cmp(ac, am) m = child am = ac end
|
|
child += 1
|
|
if child < array.size()
|
|
ac = array[child]
|
|
if cmp(ac, am) m = child am = ac end
|
|
end
|
|
if m == i break end
|
|
array[m] = array[i]
|
|
array[i] = am
|
|
i = m
|
|
end
|
|
end
|
|
|
|
# similar to C++11 std::make_heap
|
|
binary_heap.make_heap = def(array, cmp)
|
|
var i = size(array) / 2
|
|
while i >= 0 binary_heap._heapify(array, cmp, i) i -= 1 end
|
|
end
|
|
|
|
# similar to C++11 std::pop_heap, but removes and returns the element
|
|
binary_heap.remove_heap = def(array, cmp)
|
|
var m = array.size()
|
|
if m < 2 return m == 1 ? array.pop() : nil end
|
|
m = array[0]
|
|
array[0] = array.pop()
|
|
binary_heap._heapify(array, cmp, 0)
|
|
return m
|
|
end
|
|
|
|
# https://en.wikipedia.org/wiki/Heapsort
|
|
binary_heap.sort = def(array, cmp)
|
|
var i = array.size(), heap = array.copy()
|
|
binary_heap.make_heap(heap, cmp)
|
|
array.clear()
|
|
while i > 0 array.push(binary_heap.remove_heap(heap, cmp)) i -= 1 end
|
|
end
|
|
|
|
return binary_heap
|