PL/SQL doesn't have a minheap data structure.
It can be simulated with an associative array, which is sensible when you don't want to use a global temporary table and when the values in your minheap can fit within a 32bit PLS_INTEGER.
If you can use a global temporary table, a minheap is quite easy to implement and the code is very intuitive.
create global temporary table minheap(
value number
);
create index minheap_n1 on minheap (value);
DECLARE
v_value NUMBER;
FUNCTION heap_pop
RETURN PLS_INTEGER
IS
v_value PLS_INTEGER;
BEGIN
DELETE FROM minheap
WHERE 1=1
AND value = (
SELECT MIN(value)
FROM minheap
)
AND rownum = 1
RETURNING value INTO v_value
;
RETURN v_value;
END heap_pop;
PROCEDURE heap_push(
p_value PLS_INTEGER
)
IS
BEGIN
INSERT INTO minheap (
value
) VALUES (
p_value
);
END heap_push;
PROCEDURE heap_print
IS
BEGIN
FOR i IN (
SELECT value
FROM minheap
ORDER BY value
) LOOP
DBMS_OUTPUT.PUT_LINE(i.value);
END LOOP;
DBMS_OUTPUT.PUT_LINE('');
END heap_print;
BEGIN
FOR i IN 1 .. 5 LOOP
heap_push(1);
END LOOP;
heap_push(10);
heap_print();
FOR i IN 1 .. 5 LOOP
v_value := heap_pop();
v_value := v_value + i;
heap_push(v_value);
heap_print();
END LOOP;
END;
/
The query used for heap_pop is pretty good:
DELETE FROM minheap
WHERE 1=1
AND value = (
SELECT MIN(value)
FROM minheap
)
AND rownum = 1
;
Here is the execute_plan:
-------------------------------------------------------------
| Id | Operation | Name | E-Rows |
-------------------------------------------------------------
| 0 | DELETE STATEMENT | | |
| 1 | DELETE | MINHEAP | |
|* 2 | COUNT STOPKEY | | |
|* 3 | INDEX RANGE SCAN | MINHEAP_N1 | 1 |
| 4 | SORT AGGREGATE | | 1 |
| 5 | INDEX FULL SCAN (MIN/MAX)| MINHEAP_N1 | 1 |
-------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - filter(ROWNUM=1)
3 - access("VALUE"=)
The INDEX FULL SCAN(MIN/MAX) retrieves the minimum value from this table in about as fast any any SQL operation. It then makes a second index range scan with this value to get the rowid, and then finally performs the delete. It would be better if it could retrieve the max value and the rowid in one shot, but this is fast enough.