[Unified-mailman] heap code

[Howard Kleinwaks]

Students,
Attached is the heap manipulation code that were shown in class and that
you will need for pset 10.
-Howie
-------------- next part --------------
----------------------------------------------------------------
-- package implementation of heap sort
-- programmer: Jayakanth Srinivasan
-- date last modified : April 12, 2004 [IKL]
----------------------------------------------------------------

package body Heap_Sort is


   -- compute left child given parent index i
   function Left (
         I : Integer )
     return Integer is
   begin
      return(I*2);
   end Left;


   -- compute right child given parent index i
   function Right (
         I : Integer )
     return Integer is
   begin
      return(I*2+1);
   end Right;


   -- compute parent given the child index i
   function Parent (
         I : Integer )
     return Integer is
   begin
      return(I/2);
   end Parent;


   -- swap the elements at postions index I and index J
   procedure Swap (
         Heap_Array : in out My_Integer_Array;
         I          : in     Integer;
         J          : in     Integer           ) is
      Temp : Integer;
   begin
      Temp:= Heap_Array(I);
      Heap_Array(I) := Heap_Array(J);
      Heap_Array(J):= Temp;
   end Swap;


   -- ensures that the element in index I satisfies the heap property
   -- the call is recursive to ensure the correct placement of element
   -- within the subtree
   procedure Heapify (
         Heap_Array : in out My_Integer_Array;
         I          : in     Integer           ) is
      Lchild  : Integer;
      Rchild  : Integer;
      Largest : Integer;
   begin
      -- compute the values of I's children
      Lchild := Left(I);
      Rchild := Right(I);
      -- if the left child exists and it is greater than the parent
      --    remember the index of left child in largest
      --else
      --   remember the index of the parent in largest
      if (Lchild <= Heap_Size and Heap_Array(Lchild) > Heap_Array(I)) then
         Largest:= Lchild;
      else
         Largest := I;
      end if;

      -- if a right child exists, and its value is greater than element in
      -- largeset, store index of right child in largest
      if (Rchild <= Heap_Size) then
         if Heap_Array(Rchild) > Heap_Array(Largest) then
            Largest := Rchild;
         end if;
      end if;

      -- if parent does not satisfy the heap property, swap it with the
      -- largest element and repeat heapify for that location
      if (Largest /= I) then
         Swap(Heap_Array, I, Largest);
         Heapify(Heap_Array, Largest);
      end if;

   end Heapify;


   -- given an array, make it a heap
   procedure Build_Heap (
         Heap_Array : in out My_Integer_Array;
         Size       : in     Integer           ) is
   begin
      Heap_Size := Size;
      -- you only need to work backwards from the middle
      -- of the array
      for I in reverse 1 .. (Size/2) loop
         Heapify(Heap_Array, I);
      end loop;
   end Build_Heap;

end Heap_Sort;
-------------- next part --------------
----------------------------------------------------------------
-- package specification for subprograms used by heap sort
-- specifier: Jayakanth Srinivasan
-- date last modified : April 12, 2004 [IKL]
----------------------------------------------------------------

package Heap_Sort is

   type My_Integer_Array is array (1 .. 20) of Integer;
   Heap_Size : Integer;

   -- compute left child given parent index
   function Left (
         I : Integer )
     return Integer;

   -- compute right child given parent index
   function Right (
         I : Integer )
     return Integer;

   -- compute parent given the child index
   function Parent (
         I : Integer )
     return Integer;

   -- Swaps position of parent and child node
   procedure Swap (
         Heap_Array : in out My_Integer_Array;
         I          : in     Integer;
         J          : in     Integer           );

   -- Moves an element in location i, to satisfy the heap property
   procedure Heapify (
         Heap_Array : in out My_Integer_Array;
         I          : in     Integer           );

   -- Takes an (unsorted) array and makes it satisfy the heap properties
   procedure Build_Heap (
         Heap_Array : in out My_Integer_Array;
         Size       : in     Integer           );
end Heap_Sort;

-------------- next part --------------
-- test file for heap_sort.ad[bs]

with Ada.Text_Io;
with Ada.Integer_Text_Io;
use Ada.Text_Io;
use Ada.Integer_Text_Io;
with Heap_Sort;
use Heap_Sort;

procedure Test_Heap_Sort is

   Heap_Array : My_Integer_Array;
   Size       : Integer;
begin
   Size := 10;
   Put_Line("Size of Array/Heap is 10");
   for I in 1.. Size loop

      Put("Please enter a number : ");
      Get(Heap_Array(I));
      Skip_Line;
   end loop;
   New_Line;

   Put_Line("10 elements have now been added to the array");
   Put_Line("After heapifying the array:");
   Build_Heap(Heap_Array, Size);
   for I in 1 .. Size loop
      Put_Line(Integer'Image(Heap_Array(I)));
   end loop;
   New_Line;


   for I in reverse 2.. Size loop
      Swap(Heap_Array, 1, I);
      Heap_Size:= Heap_Size -1;
      Heapify(Heap_Array, 1);
   end loop;

   Put_Line("and now, time for the elements in sorted order...");
   for I in 1 .. Size loop
      Put_Line(Integer'Image(Heap_Array(I)));
   end loop;

end Test_Heap_Sort;