Developing Minimum Binary Heap In C#

Introduction to Minimum Binary Heap

At this stage, you are to be already familiar with the concept of the Minimum Binary Heap which has been discussed during the lectures. A binary heap can be considered as a special  case  of  a  binary  tree,  which  nodes  are  seen  as  building  blocks  of  the  data  structure.  The  important  fact  is  that  the  binary  heap  is  a  complete  binary  tree,  which  satisfies  the  heap  ordering property. Due to this fact, a binary heap with ? nodes always has an ??log ?? height.  In case of the “min?heap” property, the key of each node must be greater than or equal to  the key of its parent, with the minimum key element at the root.   Because  the nodes of a binary heap entirely determine its internal structure, a user is not  allowed to manipulate them, and especially their order, directly.

Therefore, there should be  an  interface  representing  the  exterior  of  the  Node  class  while  hiding  the  details  of  its  implementation. This is to be your starting point, where the first step is to develop the public interface  limiting  the methods accessible  by the  user  to  those  that are  stated in the following contract. Data  Property. Gets or sets the data of generic type D associated with a particular node  presented in a binary heap. Key  Property. Gets the key of generic type K assigned to a particular node presented in  a binary heap.  Position  Property.

Gets  the position of a particular node presented in a binary heap. The  position is equal to the index of the corresponding element placed into the array? based collection of elements internal to the binary heap. The position is an integer  number greater than or equal to 1.  Complete the interface, which primal purpose is to record and retrieve the data affiliated with  a particular node. It further allows to read the key value and track the position of the node  within the internal binary heap array.

Note that this interface is parametrized by two generic  data types: Type D stands for the data stored by the node and K determines the type of the  key. Thus, the key may have arbitrary representation, for example, be a string or long integer  number.  You can now develop the internal (private) Node class as part of the MinHeap<D,K> generic  public class representing the minimum binary heap. This means that the Node class must be  incorporated into the MinHeap<D,K> yet must implement the IHeapifyable<D,K> interface. 

With  regard  to  other  implementation  aspects  of  the  Node  class,  you  may  introduce  any  variables, properties and methods that you find necessary to complete the task and fulfil the  requirements of the subsequent MinHeap<D,K>.  Finally,  complete  the  MinHeap<D,K>  class  meeting  the  following  requirements.  Both  the  IHeapifyable<D,K> and  the MinHeap<D,K> must  be  placed  into  Project02  subfolder  of  the  project.  MinHeap(IComparer<IHeapifyable<D,K>>  comparer)  Initializes  a  new  instance  of  the  MinHeap<D,K>  class  and  records  the  specified  reference  to  the  object  that  enables  comparison  of  two  nodes,  both  implementing  the  <IHeapifyable<D,K>  interface. 

The  newly  created  instance  of  the MinHeap<D,K> class must be empty. If the MinHeap<D,K>  is empty, the Count property is set to 0. This constructor is an  ??1? operation.  Count  Property.  Gets  the  number  of  elements  contained  in  the  MinHeap<D,K>. Retrieving the value of this property is an ??1? operation.  IHeapifyable<D,K> Insert(K key, D value)  Adds a new node containing the specified key?value pair to the  MinHeap<D,K>. The position of the new element in the binary  heap is determined according the minimum binary heap policy.  Comparison of existing (and the newly added one) elements is  performed  by  the  comparator  originally  set  within  the  constructor  of  the  MinHeap<D,K>.  Returns  the  reference  of  type IHeapifyable<D,K> pointing to the newly added node. This  method is an ??log ?? operation, where ? is Count. 

Implementing Node Class with IHeapifyable interface

IHeapifyable<D,K> Min()  Returns the element yielding the minimum key, i.e. one that is  positioned  at  the  top  of  the  current  MinHeap<D,K>,  without  removing it. This method is similar to the DeleteMin() method,  but  Min()  does  not  modify  the  MinHeap<D,K>.  The  method  throws  InvalidOperationException  if  the  MinHeap<D,K>  is  empty.  The  resulting  element  is  casted  to  the  IHeapifyable<D,K>  interface  type.  This  method  is  an  ??1? operation.  IHeapifyable<D,K> DeleteMin()  Removes and  returns  the element yielding  the minimum key,  i.e.  one  that  is  positioned  at  the  top  of  the  current  MinHeap<D,K>. This method throws InvalidOperationException  if  the  MinHeap<D,K>  is  empty.  The  method  is  similar  to  the  Min() method, but Min() does not modify the MinHeap<D,K>.  The resulting node is casted to the IHeapifyable<D,K> interface type.

This method is an ??log ?? operation.  void Clear()  Removes all  nodes  from  the  current MinHeap<D,K>.  Count  is  set to zero. This method is an ???? operation.  bool IsEmpty()  Determines  whether  the  current  MinHeap<D,K>  is  empty.  It  returns true if the minimum binary heap does not contain any  element; otherwise, false. This method is an ??1? operation.  IHeapifyable<D,K>[] BuildHeap(K[] keys,  D[] data)  Builds a minimum binary heap using the specified keys and data  according to the bottom?up approach.

Every new element to be  attached to the MinHeap<D,K> is defined by the key?value pair  (keys[i],data[i]).  To  build  a  heap,  the  related  MinHeap<D,K>  must  have  no  elements,  so  this  method  throws  Invalid? OperationException  if  the  MinHeap<D,K>  is  not  empty.  The  method returns a collection of inserted elements casted to the  IHeapifyable<D,K>  interface  type.  This  method  is  an  ???? operation, where ? is the number of input data elements.   void DecreaseKey(IHeapifyable<D,K>  element, K new_key)  Decreases  the  key  of  the  specified  element  presented  in  the  current MinHeap<D,K>.

The method throws InvalidOperation? Exception  if  the  element  stored  in  the  MinHeap<D,K>  in  the  position  specified  by  the  element    given  as  an  argument  is  different to that node. This method is an ??log ?? operation.  string ToString()  Returns  a  string  that  represents  the  current  MinHeap<D,K>.  ToString()  is  the  major  formatting  method  in  the  .NET  Framework.

It converts an object to its string representation so  that it is suitable for display.  Note  that  any  operations  on  the  binary  heap  are  only  available  via  the  prescribed  public  methods and properties of the MinHeap<D,K>, which is responsible for their correctness as  well as communication with the underlying array?based structure. The internal structure of  the heap can be explored only implicitly through the positions of the nodes constituting it.  Indeed,  one  may  still  need  to  know  the  position  of  a  node  to  carry  out  such  necessary  operations  as    DecreaseKey().

Because  of  this,  the Node  class  (and  the IHeapifyable<D,K>  interface) provides Position as a read?only property. In this assignment, you should utilize the  List, which is a built?in .NET Framework class, as the internal data structure of the heap  rather  than  the  raw  array.  In  fact,  you  will  have  to  change  the  structure  of  the  array  dynamically, so List should simplify your task.   SIT221 Data Structures and Algorithms     Trimester 2, 2018  5  The MinHeap<D,K> relies on the internal comparator, which must implement the   IComparer< IHeapifyable<D,K> >   interface to make comparison of two nodes (remember that the Node class implements the  IHeapifyable<D,K>) possible. The reference to a suitable comparator is actually passed to the  constructor  and  should  be  kept  internally  by  the  MinHeap<D,K>. 

Developing Public Interface for MinHeap Class

When  the  specified  reference  is  null,  the  constructor  should  link  the  corresponding  reference  to  the  default  comparator, which can be defined as an internal class of the following form.  private class DefaultComparer : IComparer<IHeapifyable<D, K>> {    public int Compare(IHeapifyable<D, K> x, IHeapifyable<D, K> y)    {      return Comparer.Default.Compare(x.Key, y.Key);    } } In fact, this default comparator delegates the comparison process to the default comparator  for the generic type K that is affiliated with the key values. Because of this, the declaration of   MinHeap<D,K> must impose the following constraint on type K:  public class MinHeap<D, K> where K :

IComparable The DefaultComparer class is given to you as an example and you may immediately include it  into  the  MinHeap<D,K>  class.  Indeed,  you  likely  have  to  write  a  similar  code  for  the  subsequent Heap?Sort algorithm in order to adopt the minimum binary heap as a baseline  structure to sort generic objects. In this sense, you must find out a way to adopt a comparator  capable  to  compare  objects  of  type  K  to  build  a  new  comparator to  compare  the  nodes  implementing the IHeapifyable<D,K>.

Therefore, the provided example serves as a hint.  In conclusion, check the MinHeap_Test class in the Runner project. This class has already an  appropriate structure to test the required methods of the MinHeap<D,K> class. Furthermore,  Chapter  9.4  of  the  SIT221  course  book  “Data  structures  and  algorithms  in  Java”  and  the  Section  9.2.3 of Chapter  9  of  the SIT221 Workbook along with  the material of  the lecture  notes will assist you with the theory part and implementation issues of binary heaps.  Task 2. Preparing library documentation for the binary heap class.  

Access and study the materialProvide annotation for the following properties and methods of the MinHeap<D,K> class:  ? MinHeap (the constructor)  ? Count  ? Insert  ? Min  ? DeleteMin  ? BuildHeap  ? DecreaseKey  SIT221 Data Structures and Algorithms     Trimester 2, 2018  6  You must follow the general instructions explained in the article and cover all relevant aspects  of the code using the system of XML tags. Your annotation should be concise and adhere to  the  style  guidelines  that  you  have  seen  previously  for  the  built?in  libraries  of  the  .NET  Framework.

Make  sure  that  where  required  you  do  apply  multiple  tags,  for  example , , , ,  and etc. The use of particular  tags is dictated by the specificity of a method.  Task 3. Applications of the minimum binary heap  Part 3.1   Implement  the  Heap?Sort  algorithm  as  a  sorting  approach  for  a  collection  of  generic  type  objects.  Use  an  instance  of  the  MinHeap<D,K>  class  as  a  core  mechanism  producing  the  next  smallest element  during  the  solution  construction  process.  Remember  that  the  algorithm  consists  of  two  parts:  the  binary  heap  construction  and  the  iterative  extraction  of  the  top  most  elements.  The  corresponding  sorting  function  must  be  encapsulated  within  a  new  class  named  “HeapSort”  and  implement the  already  provided  ISorter interface. This will require you to give specific implementation for the expected   public void Sort(T[] sequence, IComparer comparer) where T :

IComparable method of the interface. The class must have only a default constructor. You are allowed to  add any extra private methods and attributes if necessary. The new class should be placed  into the Project02 subfolder of the attached .NET framework project.  The coding part for this task should rely on the theoretical insights that have been previously  discussed during the lectures and are presented in the corresponding lecture notes. You may  further read Chapter 9.4 of the SIT221 course book “Data structures and algorithms in Java”  to strengthen your understanding, but the version discussed there assumes in?place sorting  which is likely impossible in case of this task as you are to address the binary heap externally.  Therefore, your algorithm will probably use an auxiliary array to store intermediate results of  sorting, thus require extra ???? space. 

HINT: You will likely need to create a private class within the HeapSort class with the goal to  convert  the  IComparer  comparer  provided  as  an  argument  to  the  Sort  method  into  another  (new) one  that deals with comparison of  two IHeapifyable<D,K> elements. This is  required  since  the  MinHeap<D,K>  class  accepts  only  an  IComparer<IHeapifyable<D,K>>   based comparator.

You should adopt  the example provided in part 1 of  the assignment  to  cope with this problem. The Runner project contains the HeapSort_Test class designed to help  you with testing the Heap?Sort algorithm.  Part 3.2  People of Horsham are seeking your help. The issue is that long time ago their  town and its surrounding  roads were designed based on a  two?dimensional grid of square  cells. This forces the citizens to walk in the town strictly in one of four directions: west, east,  south, or north.

:: This file displays the printout produced by the Runner based on the official solution.

Performing: heap.Insert(9,9718) :: key value is 9 and data value is 9718
Heap: [(9,9718,1)]

Performing: heap.Insert(8,2432) :: key value is 8 and data value is 2432
Heap: [(8,2432,1),(9,9718,2)]

Performing: heap.Insert(7,7001) :: key value is 7 and data value is 7001
Heap: [(7,7001,1),(9,9718,2),(8,2432,3)]

Performing: heap.Insert(6,9122) :: key value is 6 and data value is 9122
Heap: [(6,9122,1),(7,7001,2),(8,2432,3),(9,9718,4)]

Performing: heap.Insert(5,4191) :: key value is 5 and data value is 4191
Heap: [(5,4191,1),(6,9122,2),(8,2432,3),(9,9718,4),(7,7001,5)]

Performing: heap.Insert(4,9537) :: key value is 4 and data value is 9537
Heap: [(4,9537,1),(6,9122,2),(5,4191,3),(9,9718,4),(7,7001,5),(8,2432,6)]

Performing: heap.Insert(3,7405) :: key value is 3 and data value is 7405
Heap: [(3,7405,1),(6,9122,2),(4,9537,3),(9,9718,4),(7,7001,5),(8,2432,6),(5,4191,7)]

Performing: heap.Insert(2,6495) :: key value is 2 and data value is 6495

Heap: [(2,6495,1),(3,7405,2),(4,9537,3),(6,9122,4),(7,7001,5),(8,2432,6),(5,4191,7),(9,9718,8)]

Performing: heap.Insert(1,4142) :: key value is 1 and data value is 4142
Heap: [(1,4142,1),(2,6495,2),(4,9537,3),(3,7405,4),(7,7001,5),(8,2432,6),(5,4191,7),(9,9718,8),(6,9122,9)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (1,4142)
Heap: [(2,6495,1),(3,7405,2),(4,9537,3),(6,9122,4),(7,7001,5),(8,2432,6),(5,4191,7),(9,9718,8)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (2,6495)

Heap: [(3,7405,1),(6,9122,2),(4,9537,3),(9,9718,4),(7,7001,5),(8,2432,6),(5,4191,7)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (3,7405)
Heap: [(4,9537,1),(6,9122,2),(5,4191,3),(9,9718,4),(7,7001,5),(8,2432,6)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (4,9537)
Heap: [(5,4191,1),(6,9122,2),(8,2432,3),(9,9718,4),(7,7001,5)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (5,4191)
Heap: [(6,9122,1),(7,7001,2),(8,2432,3),(9,9718,4)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (6,9122)
Heap: [(7,7001,1),(9,9718,2),(8,2432,3)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (7,7001)
Heap: [(8,2432,1),(9,9718,2)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (8,2432)
Heap: [(9,9718,1)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (9,9718)
Heap: []

Performing:heap.BuildHeap(keys, data) :: key values are [9,8,7,6,5,4,3,2,1] and data values are [9718,2432,7001,9122,4191,9537,7405,6495,4142]
Heap: [(1,4142,1),(2,6495,2),(3,7405,3),(6,9122,4),(5,4191,5),(4,9537,6),(7,7001,7),(8,2432,8),(9,9718,9)]

Performing: heap.DeleteMin() :: key-data pair of the deleted element is (1,4142)
Heap: [(2,6495,1),(5,4191,2),(3,7405,3),(6,9122,4),(9,9718,5),(4,9537,6),(7,7001,7),(8,2432,8)]

Performing value change:: for the element with key 9 new data value is 0
Performing value change:: for the element with key 2 new data value is 777
Performing value change:: for the element with key 1 new data value is -1 (not in the heap anymore)
Heap: [(2,777,1),(5,4191,2),(3,7405,3),(6,9122,4),(9,0,5),(4,9537,6),(7,7001,7),(8,2432,8)]

Performing key decreasing:: for the element with key 9 new key value must be 0
Heap: [(0,0,1),(2,777,2),(3,7405,3),(6,9122,4),(5,4191,5),(4,9537,6),(7,7001,7),(8,2432,8)]