-- Ada implementation of maxiphobic heaps as described in
--   Alternatives to Two Classic Data Structures
--   Chris Okasaki
--   SIGCSE 2005
--
-- Implements mergeable priority queues of integers.
-- Can easily be adapted to other key types.

PACKAGE Maxiphobic IS

   TYPE Heap_Type IS PRIVATE;

   PROCEDURE Insert(Value : Integer; Heap : IN OUT Heap_Type);
   PROCEDURE Merge(Heap1, Heap2 : IN OUT Heap_Type); -- merge Heap2 into Heap1

   Empty_Exception : EXCEPTION; -- raised by Find_Min/Delete_Min

   FUNCTION Find_Min(Heap : Heap_Type) RETURN Integer;
   PROCEDURE Delete_Min(Heap : IN OUT Heap_Type);

   FUNCTION Size(Heap : Heap_Type) RETURN Natural;

PRIVATE

   TYPE Tree_Node;
   TYPE Tree_Ptr IS ACCESS Tree_Node;
   TYPE Tree_Node IS RECORD
      Value : Integer;
      Size : Natural;
      Left, Right : Tree_Ptr;
   END RECORD;

   TYPE Heap_Type IS RECORD
      Root : Tree_Ptr := null;
   END RECORD;

END Maxiphobic;