PL/SQL does not have a minheap collection type.
We can simulate it using a global temporary table trivially. But if we don't want to use a global temporary table, and the values in our minheap are small enough to fit within a 32bit PLS_INTEGER, then we can use an associative table.
Associative tables store values in sorted order, not in insertion order, so calling l_foos.FIRST will always return the smallest key in an associative table. Associative tables are essentially a sorted tree.
Using this, we can hack together a data structure that resembles a minheap.
There are a few issues with this approach.
First is when you have two items in the minheap that contain the same value. Both will require the same index, so we need to have the associative table index the value to a record containing the value and the count:
TYPE r_entry IS RECORD (
value NUMBER,
count NUMBER
);
TYPE t_minheap IS TABLE OF r_entry INDEX BY PLS_INTEGER;
This adds complexity, as we now need to manage the entry, decrementing the count when we pop from the heap, and removing the entry entirely when the count drops to 0; as well as checking if there is an entry and adding it if not while pushing to the heap, and incrementing the count.
The second issue is that this only works for PLS_INTEGER which holds 32bit integers, and will not work for anything larger. Associative arrays only support INDEX BY PLS_INTEGER or INDEX BY VARCHAR2. Normally if you need to index by a 64bit integer you can simply INDEX BY VARCHAR2(45) and pass in large integers:
DECLARE
TYPE t_aa IS TABLE OF NUMBER INDEX BY VARCHAR2(45);
v_aa t_aa;
BEGIN
v_aa(9223372036854775807) := 9223372036854775807;
END;
/
This will not work for our simulated minheap, however, since we are depending on the sorted order. Oracle will store this in lexicographical order which will be wrong. For example assuming NLS_SORT and NLS_COMP are BINARY, the following code prints 10 instead of 2:
DECLARE
TYPE t_tab IS TABLE OF NUMBER INDEX BY VARCHAR2(45);
v_tab t_tab;
v_index VARCHAR2(45);
BEGIN
v_tab(2) := 2;
v_tab(10) := 10;
v_index := v_tab.FIRST;
DBMS_OUTPUT.PUT_LINE(v_index);
END;
/
So we are stuck with only being able to handle PLS_INTEGER and 32 bit integers.
With that out of the way, here is the code to simulate a minheap using associative arrays in PL/SQL:
DECLARE
TYPE r_entry IS RECORD (
value PLS_INTEGER,
count NUMBER
);
TYPE t_minheap IS TABLE OF r_entry INDEX BY PLS_INTEGER;
v_minheap t_minheap;
v_value PLS_INTEGER;
FUNCTION heap_pop(
p_minheap IN OUT NOCOPY t_minheap
)
RETURN PLS_INTEGER
IS
v_value PLS_INTEGER;
BEGIN
IF p_minheap.COUNT = 0 THEN
RETURN NULL;
END IF;
v_value := p_minheap(p_minheap.FIRST).value;
p_minheap(p_minheap.FIRST).count := p_minheap(p_minheap.FIRST).count - 1;
IF p_minheap(p_minheap.FIRST).count = 0 THEN
p_minheap.DELETE(p_minheap.FIRST);
END IF;
RETURN v_value;
END heap_pop;
PROCEDURE heap_push(
p_minheap IN OUT NOCOPY t_minheap,
v_value PLS_INTEGER
)
IS
BEGIN
IF p_minheap.EXISTS(v_value) THEN
p_minheap(v_value).count := p_minheap(v_value).count + 1;
ELSE
p_minheap(v_value) := r_entry(v_value, 1);
END IF;
END heap_push;
PROCEDURE heap_print(
p_minheap t_minheap
)
IS
l_index PLS_INTEGER;
BEGIN
IF p_minheap.COUNT = 0 THEN
RETURN;
END IF;
l_index := p_minheap.FIRST;
WHILE l_index IS NOT NULL LOOP
FOR i IN 1 .. p_minheap(l_index).count LOOP
DBMS_OUTPUT.PUT_LINE(p_minheap(l_index).value);
END LOOP;
l_index := p_minheap.NEXT(l_index);
END LOOP;
DBMS_OUTPUT.PUT_LINE('');
END heap_print;
BEGIN
FOR i IN 1 .. 5 LOOP
heap_push(v_minheap, 1);
END LOOP;
heap_push(v_minheap, 10);
heap_print(v_minheap);
FOR i IN 1 .. 5 LOOP
v_value := heap_pop(v_minheap);
v_value := v_value + i;
heap_push(v_minheap, v_value);
heap_print(v_minheap);
END LOOP;
END;
/
Running this gives:
1
1
1
1
1
10
1
1
1
1
2
10
1
1
1
2
3
10
1
1
2
3
4
10
1
2
3
4
5
10
2
3
4
5
6
10
You might wonder why I do this:
v_minheap(v_minheap.FIRST).count := v_minheap(v_minheap.FIRST).count - 1;
Instead of this:
IS
v_entry t_entry;
BEGIN
v_entry = v_minheap(v_minheap.FIRST);
...
v_entry.count := v_entry.count + 1
...
Unfortunately PL/SQL will always make a copy. So the v_entry does not contain a reference to the actual entry in the v_minheap. The only way around this is to copy it back:
v_minheap(v_minheap.FIRST) := v_entry;
However these copy operations are expensive and should be avoided.
Using NOCOPY will not solve this problem