blob: 05fd452f3351d527a55f035d4cc7b75ddaa9ae34 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
/* $Id$ */
/**
* Binary Heap.
* Peek and Pop always return the current lowest value in the list.
* Sort is done on insertion and on deletion.
*/
class Binary_Heap
{
_queue = null;
_count = 0;
constructor()
{
_queue = [];
}
/**
* Insert a new entry in the list.
* The complexity of this operation is O(ln n).
* @param item The item to add to the list.
* @param priority The priority this item has.
*/
function Insert(item, priority);
/**
* Pop the first entry of the list.
* This is always the item with the lowest priority.
* The complexity of this operation is O(ln n).
* @return The item of the entry with the lowest priority.
*/
function Pop();
/**
* Peek the first entry of the list.
* This is always the item with the lowest priority.
* The complexity of this operation is O(1).
* @return The item of the entry with the lowest priority.
*/
function Peek();
/**
* Get the amount of current items in the list.
* The complexity of this operation is O(1).
* @return The amount of items currently in the list.
*/
function Count();
/**
* Check if an item exists in the list.
* The complexity of this operation is O(n).
* @param item The item to check for.
* @return True if the item is already in the list.
*/
function Exists(item);
};
function Binary_Heap::Insert(item, priority)
{
/* Append dummy entry */
_queue.append(0);
_count++;
local hole;
/* Find the point of insertion */
for (hole = _count - 1; hole > 0 && priority <= _queue[hole / 2][1]; hole /= 2)
_queue[hole] = _queue[hole / 2];
/* Insert new pair */
_queue[hole] = [item, priority];
return true;
}
function Binary_Heap::Pop()
{
if (_count == 0) return null;
local node = _queue[0];
/* Remove the item from the list by putting the last value on top */
_queue[0] = _queue[_count - 1];
_queue.pop();
_count--;
/* Bubble down the last value to correct the tree again */
_BubbleDown();
return node[0];
}
function Binary_Heap::Peek()
{
if (_count == 0) return null;
return _queue[0][0];
}
function Binary_Heap::Count()
{
return _count;
}
function Binary_Heap::Exists(item)
{
/* Brute-force find the item (there is no faster way, as we don't have the priority number) */
foreach (node in _queue) {
if (node[0] == item) return true;
}
return false;
}
function Binary_Heap::_BubbleDown()
{
if (_count == 0) return;
local hole = 1;
local tmp = _queue[0];
/* Start switching parent and child until the tree is restored */
while (hole * 2 < _count + 1) {
local child = hole * 2;
if (child != _count && _queue[child][1] <= _queue[child - 1][1]) child++;
if (_queue[child - 1][1] > tmp[1]) break;
_queue[hole - 1] = _queue[child - 1];
hole = child;
}
/* The top value is now at his new place */
_queue[hole - 1] = tmp;
}
|
