| 1 |
function compareArea(a, b) { |
| 2 |
return a[1][2] - b[1][2]; |
| 3 |
} |
| 4 |
|
| 5 |
export default function() { |
| 6 |
var heap = {}, |
| 7 |
array = [], |
| 8 |
size = 0; |
| 9 |
|
| 10 |
heap.push = function(object) { |
| 11 |
up(array[object._ = size] = object, size++); |
| 12 |
return size; |
| 13 |
}; |
| 14 |
|
| 15 |
heap.pop = function() { |
| 16 |
if (size <= 0) return; |
| 17 |
var removed = array[0], object; |
| 18 |
if (--size > 0) object = array[size], down(array[object._ = 0] = object, 0); |
| 19 |
return removed; |
| 20 |
}; |
| 21 |
|
| 22 |
heap.remove = function(removed) { |
| 23 |
var i = removed._, object; |
| 24 |
if (array[i] !== removed) return; // invalid request |
| 25 |
if (i !== --size) object = array[size], (compareArea(object, removed) < 0 ? up : down)(array[object._ = i] = object, i); |
| 26 |
return i; |
| 27 |
}; |
| 28 |
|
| 29 |
function up(object, i) { |
| 30 |
while (i > 0) { |
| 31 |
var j = ((i + 1) >> 1) - 1, |
| 32 |
parent = array[j]; |
| 33 |
if (compareArea(object, parent) >= 0) break; |
| 34 |
array[parent._ = i] = parent; |
| 35 |
array[object._ = i = j] = object; |
| 36 |
} |
| 37 |
} |
| 38 |
|
| 39 |
function down(object, i) { |
| 40 |
while (true) { |
| 41 |
var r = (i + 1) << 1, |
| 42 |
l = r - 1, |
| 43 |
j = i, |
| 44 |
child = array[j]; |
| 45 |
if (l < size && compareArea(array[l], child) < 0) child = array[j = l]; |
| 46 |
if (r < size && compareArea(array[r], child) < 0) child = array[j = r]; |
| 47 |
if (j === i) break; |
| 48 |
array[child._ = i] = child; |
| 49 |
array[object._ = i = j] = object; |
| 50 |
} |
| 51 |
} |
| 52 |
|
| 53 |
return heap; |
| 54 |
} |