Coding Challenge 13

In this tutorial, we are going to discover the Heap data structure. In the previous post, we learned the queue data structure. A heap is an implementation of the priority queue that does not apply the first in last out principle because the priority queue removes items depending on their priority. There are two types of heaps :max heaps and min heaps. After analysing MaxHeap with me, please try to do MinHeap.

Max Heaps

If you run the following code, you will see in detail what we did at all stages.

program.cs

MaxHeap mheap = new MaxHeap(new int[] { 1, 2, 3, 4, 5, 6 }, 6);
mheap.MaxHeapify(3);
Console.WriteLine(mheap.ToString());

Max Heaps class

I printed each line in detail to show all processes step by step.

 public class MaxHeap
    {
        public MaxHeap(int[] input, int length)// This is a constructor
        {
            this.Length = length;
            this.Array = input;
            BuildMaxHeap();
        }

        public int[] Array { get; private set; }

        public int Length { get; private set; }

        private void BuildMaxHeap()
        {
            Console.WriteLine("Started Building Max Heap");
            Console.WriteLine("Divided two length of array and loop throuh it");
            for (int i = this.Length / 2; i > 0; i--)
            {
                Console.WriteLine($"Started i: {i}");
                MaxHeapify(i);
                Console.WriteLine($"Finished i: {i}\n");
            }

            return;
        }


        /// <summary>
        /// Heapify is the process of creating a heap data structure from a binary tree. Here, we used heapify to create MaxHeapify.
        /// </summary>
        /// <param name="index"></param>
        public void MaxHeapify(int index)
        {
            var left = 2 * index;
            var right = 2 * index + 1;
            
            Console.WriteLine($"Left : {left} Right: {right}");
            int max = index;
            if (left <= this.Length && this.Array[left - 1] > this.Array[index - 1])
            {
                Console.WriteLine($"Left: {left} this.Array[{left - 1}]: {this.Array[left - 1]} this.Array[{index-1}]: {this.Array[index - 1]}");

                max = left;
            }

            if (right <= this.Length && this.Array[right - 1] > this.Array[max - 1])
            {
                Console.WriteLine($"Right: {right} this.Array[{right - 1}]: {this.Array[right - 1]} this.Array[{index - 1}]: {this.Array[max - 1]}");

                max = right;
            }

            if (max != index)
            {
                Console.Write("Array:");
                foreach (var item in this.Array)
                {
                    Console.Write(" "+item);
                }
                Console.WriteLine("\n <-----Wrapping Time----->");
                Console.WriteLine($"Index: {index} this.Array[{index - 1}]: {this.Array[index - 1]}");
                int temp = this.Array[max - 1];
                this.Array[max - 1] = this.Array[index - 1];
                this.Array[index - 1] = temp;
                Console.WriteLine($"Index: {index} this.Array[{index-1}]: {this.Array[index-1]}");

                Console.WriteLine(ToString());
                MaxHeapify(max);
            }

            return;
        }

        public int RemoveMaximum()
        {
            int maximum = this.Array[0];

            this.Array[0] = this.Array[this.Length - 1];
            this.Length--;
            MaxHeapify(1);
            return maximum;
        }
        public override string ToString()
        {
            string str = "";
            foreach (var item in this.Array)
            {
                str += item+"-";
            }
            return str;
        }
    }

OutPut:

Started Building Max Heap
Divided two length of array and loop through it
Started i: 3
Left : 6 Right: 7
Left: 6 this.Array[5]: 6 this.Array[2]: 3
Array: 1 2 3 4 5 6
 <-----Wrapping Time----->
Index: 3 this.Array[2]: 3
Index: 3 this.Array[2]: 6
1-2-6-4-5-3-
Left : 12 Right: 13
Finished i: 3

Started i: 2
Left : 4 Right: 5
Left: 4 this.Array[3]: 4 this.Array[1]: 2
Right: 5 this.Array[4]: 5 this.Array[1]: 4
Array: 1 2 6 4 5 3
 <-----Wrapping Time----->
Index: 2 this.Array[1]: 2
Index: 2 this.Array[1]: 5
1-5-6-4-2-3-
Left : 10 Right: 11
Finished i: 2

Started i: 1
Left : 2 Right: 3
Left: 2 this.Array[1]: 5 this.Array[0]: 1
Right: 3 this.Array[2]: 6 this.Array[0]: 5
Array: 1 5 6 4 2 3
 <-----Wrapping Time----->
Index: 1 this.Array[0]: 1
Index: 1 this.Array[0]: 6
6-5-1-4-2-3-
Left : 6 Right: 7
Left: 6 this.Array[5]: 3 this.Array[2]: 1
Array: 6 5 1 4 2 3
 <-----Wrapping Time----->
Index: 3 this.Array[2]: 1
Index: 3 this.Array[2]: 3
6-5-3-4-2-1-
Left : 12 Right: 13
Finished i: 1

Left : 6 Right: 7
6-5-3-4-2-1-