In writing one of my scripts, I found that I wanted a priority queue. A naive ASH implementation using sort resulted in n log n cost to retrieve an element, which is hideously bad (with 1 million elements, that's about 20 million comparisons, as opposed to the desired 20 or so). After a bit of whining to myself, I sucked it up and implemented a priority heap in ASH. I'm posting this here in the hope that someone else might find it useful.
I don't *think* it's buggy (I ran some number of tests on it), although I could be mistaken.
I don't *think* it's buggy (I ran some number of tests on it), although I could be mistaken.
PHP:
record Heap {
string [int] heap;
float [string] cost;
};
void add(Heap h, string value, float cost) {
h.cost[""] = 2.0 ** 1023 * 2; // infinity; can substitute some other large number here
int index = count(h.heap);
h.heap[index] = value;
h.cost[value] = cost;
while (cost < h.cost[h.heap[index / 2]]) {
h.heap[index] = h.heap[index / 2];
index /= 2;
h.heap[index] = value;
}
}
string poll(Heap h) {
string ret = h.heap[0];
int index;
while (index < count(h.heap)) {
h.heap[index] = "";
if (h.heap[2*index+1] != "" && h.cost[h.heap[2*index + 1]] < h.cost[h.heap[2*index + 2]]) {
h.heap[index] = h.heap[2*index+1];
index = 2*index + 1;
} else {
h.heap[index] = h.heap[2*index+2];
index = 2*index + 2;
}
}
return ret;
}